本题考查的树的直径的求法,树的直径有两种求法
其中一种参见 树的最长路径
而该题只需由根bfs至离根最远的点而后再次bfs即可
如下为代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 4e4 + 10;
int h[N],e[N],ne[N],w[N],idx;
int d[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void bfs(int root){
queue<int>q;
q.push(root);
d[root] = 0;
while(q.size()){
int t = q.front();
st[t] = true;
q.pop();
for(int i=h[t];~i;i=ne[i]){
int j = e[i];
if(st[j]) continue;
d[j] = d[t] + 1;
st[j] = true;
q.push(j);
}
}
}
int main(){
memset(h,-1,sizeof h);
cin >> n >> m;
for(int i=2;i<=n;i++){
int r;
cin >> r;
add(i,r,1);
add(r,i,1);
}
for(int i=n+1;i<=m+n;i++){
int r;
cin >> r;
add(i,r,1);
add(r,i,1);
}
bfs(1);
int root = 0,cur = 0,ans = 0;
for(int i=1;i<=m+n;i++){
if(d[i] > cur){
root = i;
cur = d[i];
}
}
memset(d,0,sizeof d);
memset(st,false,sizeof st);
bfs(root);
for(int i=1;i<=m+n;i++) ans = max(ans,d[i]);
cout << ans << endl;
return 0;
}