问题描述
给定一个公司的网络，由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
样例输入
4 4
1 2 2
3 4 4 4
样例输出
4
解题思路：
首先，对于所有节点，找出，以此节点为跟根节点的最大深度h1，次大深度h2;h1+h2为以此节点为根节点子树中经过此节点的最大路径长度；
然后，遍历所有节点，找出，整棵树的最大路径长度；
动态规划过程：
父节点f,有k个子节点ci；
当k>=2时，
f.h1=max(ci.h1) for all 1<=i<=k;
f.h2=second_max(ci.h1);for all 1<=i<=k;
当k1时；
f.h1=c1.h1;
f.h2=0;
当k0时
f.h1=0;
f.h2=0;
通过代码：
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;
int n, m, nm;
vector<int>a[20001];//保存a[i]代表a[i]子节点的下标集合；
int f[20001];//保存节点父节点下标；
char b[20001];//保存节点的访问状态；
class Nod {
public:
int h1, h2;
};
Nod nod[20001];//nod[i]保存节点i的h1最大子树高度和h2次高度；
void getAns() {
memset(b,0,sizeof(b));
b[1] = 1;
stack<int>q;
q.push(1);
int cur = -1;
int len = 0;
bool find ;
while (!q.empty()) {//迭代版dfs,防止数据过大，栈溢出；
cur = q.top();
find = false;
len = a[cur].size();
for (int i = 0; i < len; ++i) {
if (b[a[cur][i]] == 0) {
find = true;
b[a[cur][i]] = 1;
q.push(a[cur][i]);
}
}
if (!find) {//当某个节点子节点访问完毕，弹出时，更新父节点的最大子树高度，次高度；
q.pop();
int p_index = f[cur];
if (p_index == 0) {//如果父节点下标为0，表明到达根路由器，退出dfs；
break;
}
int temp_h = nod[cur].h1+1;
if ( temp_h> nod[p_index].h1) {
nod[p_index].h2 = nod[p_index].h1;
nod[p_index].h1 = temp_h;
}
else if (temp_h>nod[p_index].h2) {
nod[p_index].h2 = temp_h;
}
}
}
int ans = 0;
int temp = 0;
for (int i = 1; i <= nm; ++i) {//寻找进过最长路径;
temp = nod[i].h1 + nod[i].h2;
if (temp > ans) {
ans = temp;
}
}
cout << ans << endl;
}
void input() {
cin >> n >>m;
nm = n + m;
memset(f, 0, sizeof(f));
int p;
for (int i = 2; i <= n; ++i) {
cin >> p;
a[p].push_back(i);
f[i] = p;
}
for (int i = n+1; i <= nm; ++i) {
cin >> p;
a[p].push_back(i);
f[i] = p;
}
getAns();
}
int main(){
input();
return 0;
}