树形DP

这道题是1072. 树的最长路径模板题

做图论题最重要的就是将题目含义抽象出来，即建图的过程。这道题一眼就能就能看出来，将电脑和交换机都当成节点，题目的答案就抽象成求两个最远叶节点的距离，用树形DP就可以做。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int e[N] , ne[N] , h[N] , idx;
int f[N];//f[u]表示u到最远叶节点的距离。显然如果u是节点，则f[u]=0。
int n , m , ans;

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

void dfs(int u)//求以u为根节点到叶节点的最大距离
{
    int a = 0 , b = 0;//a记录u到最远叶节点的距离，b记录u到次远叶节点的距离
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        //求子节点j到最远叶节点的距离
        dfs(j);

        int t = f[j] + 1;//u通过j能到的最远叶节点的距离

        //更新a、b
        if(t >= a)
            b = a , a = t;
        else if(t > b)
            b = t;
    }

    f[u] = a;
    //最后的答案就是u所能到的最远叶节点距离和次远叶节点距离之和
    ans = max(ans , a + b);
}

int main()
{
    cin >> n >> m;

    memset(h , -1 , sizeof h);
    //电脑其实和交换机等价，所以电脑的标号从n继续往后标记即可
    for(int i = 2 ; i <= n + m ; i++)
    {
        int j;
        cin >> j;
        add(j , i);//因为是自根向下DP，所以建一条边即可。
    }

    dfs(1);

    cout << ans << endl;
}