CCF認證 2015-03-4 網絡延時
思路：求樹的直徑，兩次bfs，一次任意起點找出最遠那個點s，由此點bfs找到最遠的t，s-t的距離即位答案。
問題描述
給定一個公司的網絡，由n台交換機和m台終端電腦組成，交換機與交換機、交換機與電腦之間使用網絡連接配接。交換機按層級設定，編号為1的交換機為根交換機，層級為1。其他的交換機都連接配接到一台比自己上一層的交換機上，其層級為對應交換機的層級加1。所有的終端電腦都直接連接配接到交換機上。
當資訊在電腦、交換機之間傳遞時，每一步隻能通過自己傳遞到自己所連接配接的另一台電腦或交換機。請問，電腦與電腦之間傳遞消息、或者電腦與交換機之間傳遞消息、或者交換機與交換機之間傳遞消息最多需要多少步。
輸入格式
輸入的第一行包含兩個整數n, m，分别表示交換機的台數和終端電腦的台數。
第二行包含n - 1個整數，分别表示第2、3、……、n台交換機所連接配接的比自己上一層的交換機的編号。第i台交換機所連接配接的上一層的交換機編号一定比自己的編号小。
第三行包含m個整數，分别表示第1、2、……、m台終端電腦所連接配接的交換機的編号。
輸出格式
輸出一個整數，表示消息傳遞最多需要的步數。
樣例輸入
4 2
1 1 3
2 1
樣例輸出
4
樣例說明
樣例的網絡連接配接模式如下，其中圓圈表示交換機，方框表示電腦：
其中電腦1與交換機4之間的消息傳遞花費的時間最長，為4個機關時間。
樣例輸入
4 4
1 2 2
3 4 4 4
樣例輸出
4
樣例說明
樣例的網絡連接配接模式如下：
其中電腦1與電腦4之間的消息傳遞花費的時間最長，為4個機關時間。
評測用例規模與約定
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=20000+10;
vector<int>tree[maxn];
int dis[maxn];
//樹的直徑
//找到随意一點最遠的點，兩次dfs
int main()
{
int n,m,a;
scanf("%d%d",&n,&m);
for(int i=2;i<=n+m;i++)
{
scanf("%d",&a);
tree[a].push_back(i);
tree[i].push_back(a);//雙向連接配接
}
queue<int>q;
memset(dis,-1,sizeof(dis));
int s=1;
q.push(s);
dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
s=u;//記錄每次廣搜的結果，最後出來的是最遠的
int len=tree[u].size();
for(int i=0;i<len;i++)
{
if(dis[tree[u][i]]==-1)
{
dis[tree[u][i]]=dis[u]+1;
q.push(tree[u][i]);
}
}
}
memset(dis,-1,sizeof(dis));
q.push(s);
dis[s]=0;
while(!q.empty())
{
int u=q.front();q.pop();
s=u;//記錄每次廣搜的結果，最後出來的是最遠的
int len=tree[u].size();
for(int i=0;i<len;i++)
{
if(dis[tree[u][i]]==-1)
{
dis[tree[u][i]]=dis[u]+1;
q.push(tree[u][i]);
}
}
}
printf("%d\n",dis[s]);
return 0;
}