两次深搜
第一次随便挑一个电脑,然后找此电脑对应最远的那个叶子结点
然后再从该叶子结点出发,找到的最长路径就是答案
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 10000;
vector<int> a[20005];
int book[MAXN*2+5];
int Max;
int node1;
void dfs(int now,int cnt)
{
if(cnt && a[now].size() == 1)//到达另外一台电脑
{
if(cnt > Max)
{
node1 = now;
Max = cnt;
}
return ;
}
book[now] = 1;
for(int i=0;i<a[now].size();i++)
{
int ne = a[now][i];
if(!book[ne])
dfs(ne,cnt+1);
}
book[now] = 0;
return ;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int ou[20005] = {0};
for(int i=2;i<=n;i++)
{
int fa;
scanf("%d",&fa);
a[fa].push_back(i);
a[i].push_back(fa);
// ou[fa]++;
}
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
a[x].push_back(i+MAXN);
a[i+MAXN].push_back(x);
// ou[x]++;
}
dfs(MAXN+1,0);
dfs(node1,0);
cout<<Max;
return 0;
}