問題鏈接：CCF201503試題。

問題描述：

  給定一個公司的網(wǎng)絡，由n臺交換機和m臺終端電腦組成，交換機與交換機、交換機與電腦之間使用網(wǎng)絡連接。交換機按層級設置，編號為1的交換機為根交換機，層級為1。其他的交換機都連接到一臺比自己上一層的交換機上，其層級為對應交換機的層級加1。所有的終端電腦都直接連接到交換機上。

  當信息在電腦、交換機之間傳遞時，每一步只能通過自己傳遞到自己所連接的另一臺電腦或交換機。請問，電腦與電腦之間傳遞消息、或者電腦與交換機之間傳遞消息、或者交換機與交換機之間傳遞消息最多需要多少步。

  輸入的第一行包含兩個整數(shù)n, m，分別表示交換機的臺數(shù)和終端電腦的臺數(shù)。  第二行包含n - 1個整數(shù)，分別表示第2、3、……、n臺交換機所連接的比自己上一層的交換機的編號。第i臺交換機所連接的上一層的交換機編號一定比自己的編號小。  第三行包含m個整數(shù)，分別表示第1、2、……、m臺終端電腦所連接的交換機的編號。  輸出一個整數(shù)，表示消息傳遞最多需要的步數(shù)。

問題分析：這是一個樹的問題，求樹的直徑，即在樹中找出兩個結點，使得這兩個結點間的距離最長，這個最長距離稱為直徑。一般可以用兩次DFS或BFS來實現(xiàn)，在樹上任意選取1個結點s，先用DFS或BFS找到距離s距離最遠的結點start，然后再從結點start開始，再次用DFS或BFS找到距離s距離最遠的結點，得到結果。

程序說明：樹用鄰接結點來存儲，使用STL的向量數(shù)組vector<int> tree[]來表示，tree[i]中的存儲從結點i能夠到達的各個結點。其他說明參見源程序。

用整數(shù)表示結點，結點號是不允許重復的。終端電腦的變化從n+1開始，依次類推。

參考鏈接：HDU4607 Park Visit（解法二）。

提交后得100分的C++語言程序如下：

/* CCF201503-4 網(wǎng)絡延時 */#include <iostream>#include <vector>#include <cstring>using namespace std;// 深度優(yōu)先搜索：計算結點now到各個結點的距離，結果放入數(shù)組d[]中void dfs(int now, int last, int d[], vector<int> tree[]){    int u, size;    size = tree[now].size();    for(int i=0; i<size; i++)        if ((u = tree[now][i]) != last) {            d[u] = d[now] + 1;            dfs(u, now, d, tree);        }}int main(){    int n, m, t;    // 輸入數(shù)據(jù)，構建樹（鄰接圖）    cin >> n >> m;    vector<int> tree[n+m+2];    int dist[n+m+2];    for(int i=2; i<=n; i++) {        cin >> t;        tree[i].push_back(t);        tree[t].push_back(i);    }    for(int i=1; i<=m; i++) {        cin >> t;        tree[n+i].push_back(t);        tree[t].push_back(n+i);    }    // 求結點1到各個結點的距離：距離放在數(shù)組dist[]中，dist[i]中存放結點1到結點i的距離    memset(dist, 0, sizeof(dist));    dfs(1, 0, dist, tree);    // 找出距離結點1最遠的結點start    int start = 0;    dist[start] = 0;    for(int i=1; i<n+m+2; i++)        if(dist[i] > dist[start])            start = i;    // 求start結點到各個結點的距離：距離放在數(shù)組dist[]中，dist[i]中存放結點start到結點i的距離    memset(dist, 0, sizeof(dist));    dfs(start, 0, dist, tree);    // 找出距離結點start最遠的結點target    int target = 0;    for (int i=1; i<n+m+2; i++)        if(dist[i] > dist[target])            target = i;    // 輸出結果    cout << dist[target] << endl;    return 0;}