算法

(树形Dp) $O(n)$

本题用到性质：一棵树中，一个点必然与直径的两个端点中的一个相距最远
然后就求直径两个端点即可，可以不用树形Dp，直接用SPFA算法按照传统的求法写(要是毒瘤出题人直接换根，参考提高课1072题的讲解即可)
然后就AC了，复杂度线性
代码是没有卡常的版本，卡常的版本在这里

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#define maxn 10010

using namespace std;

int n;
int p, q;
bool st[maxn];
int ans[maxn];
int h[maxn], e[maxn * 2], w[maxn * 2], ne[maxn * 2], idx;
int dist[maxn];

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

void spfa(int s)
{
    queue<int> q;
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    q.push(s);

    while (q.size())
    {
        int t = q.front(); q.pop();
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    st[j] = 1;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    while (cin >> n)
    {
        idx = 0;
        memset(h, -1, sizeof h);

        for (int i = 2; i <= n; i ++ )
        {
            int a, b;
            cin >> a >> b;
            add(a, i, b), add(i, a, b);
        }

        spfa(1);
        int maxv = -1e9;
        for (int i = 1; i <= n; i ++ )
            if (maxv < dist[i])
                maxv = dist[i], p = i;
        spfa(p);
        maxv = -1e9;
        for (int i = 1; i <= n; i ++ )
            if (maxv < dist[i])
                maxv = dist[i], q = i;
        for (int i = 1; i <= n; i ++ ) ans[i] = dist[i];
        spfa(q);

        for (int i = 1; i <= n; i ++ ) cout << max(ans[i], dist[i]) << endl;
    }

    return 0;
}