問題鏈接：CCF201503試題。

問題描述：

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

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

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

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

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

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

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

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

/* CCF201503-4 網(wǎng)絡(luò)延時 */#include <iostream>#include <vector>#include <cstring>using namespace std;// 深度優(yōu)先搜索：計(jì)算結(jié)點(diǎn)now到各個結(jié)點(diǎn)的距離，結(jié)果放入數(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ù)，構(gòu)建樹（鄰接圖）    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);    }    // 求結(jié)點(diǎn)1到各個結(jié)點(diǎn)的距離：距離放在數(shù)組dist[]中，dist[i]中存放結(jié)點(diǎn)1到結(jié)點(diǎn)i的距離    memset(dist, 0, sizeof(dist));    dfs(1, 0, dist, tree);    // 找出距離結(jié)點(diǎn)1最遠(yuǎn)的結(jié)點(diǎn)start    int start = 0;    dist[start] = 0;    for(int i=1; i<n+m+2; i++)        if(dist[i] > dist[start])            start = i;    // 求start結(jié)點(diǎn)到各個結(jié)點(diǎn)的距離：距離放在數(shù)組dist[]中，dist[i]中存放結(jié)點(diǎn)start到結(jié)點(diǎn)i的距離    memset(dist, 0, sizeof(dist));    dfs(start, 0, dist, tree);    // 找出距離結(jié)點(diǎn)start最遠(yuǎn)的結(jié)點(diǎn)target    int target = 0;    for (int i=1; i<n+m+2; i++)        if(dist[i] > dist[target])            target = i;    // 輸出結(jié)果    cout << dist[target] << endl;    return 0;}