AC代码

为什么在dfs函数的最后要return d1+1 ， 这里为什么要＋1？

因为本题中的计算机和交换机是节点，比路径加一

#include<bits/stdc++.h>
using namespace std;

const int N = 20010,M=N;    //本题有两种机器，每种是10010，
int h[N],e[M],ne[M],idx;
int ans;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)  //惯用u
{
    int d1=0,d2=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        int d=dfs(j);
        if(d>=d1)
        {
            d2=d1,d1=d;
        }
        else if(d>d2) d2=d;
    }   //{}结束就意味着已经找出了d1,d2
    ans = max(ans,d2+d1);
    return d1+1;
}

int main()
{
    int n,m;
    cin>>n>>m;
    memset(h,-1,sizeof h);  //使用树数组必须初始化链表头
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        add(x,i);
    }
    for(int i=n+1;i<=n+m;i++)
    {
        int x;
        cin>>x;
        add(x,i);
    }
    dfs(1);
    cout<<ans;
}