算法

(树的直径) $O(nlogn)$

提供一个和其他题解不一样的思路
到每一个点的最远点一定是直径的两端u/v，这个很好证明
把直径求出来过后对每个点求到u，v的最远距离即可

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
#define ll long long
int n,dis[N],d[N],f[N][20],vis[N];
ll g[N][20];
vector<int>to[N],v[N];
void Clear()
{
    for(int i=1;i<=N-5;i++)to[i].clear(),v[i].clear(),d[i]=0;
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
}
void Dfs(int x,int fa)
{
    d[x]=d[fa]+1;
    for(int i=1;i<=log(n)/log(2);i++)
    if(f[x][i-1])f[x][i]=f[f[x][i-1]][i-1],g[x][i]=g[x][i-1]+g[f[x][i-1]][i-1];
    for(int i=0;i<to[x].size();i++)
    {
        int y=to[x][i];
        if(y==fa)continue;
        f[y][0]=x;
        g[y][0]=v[x][i];
        Dfs(y,x);
    }
}
int Bfs(int s)
{
    memset(dis,0,sizeof(dis));
    queue<int>q;
    q.push(s);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=0;i<to[x].size();i++)
        {
            int y=to[x][i];
            if(dis[y])continue;
            dis[y]=dis[x]+v[x][i];
            q.push(y);
        }
    }
    int k=0;
    for(int i=1;i<=n;i++)if(!k||dis[k]<dis[i])k=i;
    return k;
}
ll Lca(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    int k=log(d[x])/log(2);
    ll ans=0;
    for(int i=k;i>=0;i--)
        if(f[x][i]&&d[f[x][i]]>=d[y])ans+=g[x][i],x=f[x][i];
    if(x==y)return ans;
    for(int i=k;i>=0;i--)
        if(f[x][i]&&f[x][i]!=f[y][i])ans+=g[x][i]+g[y][i],x=f[x][i],y=f[y][i];
    return ans+g[x][0]+g[y][0];
}
int main()
{
    while(~scanf("%d",&n))
    {
        Clear();
        for(int i=2;i<=n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            to[x].push_back(i);
            v[x].push_back(y);
            to[i].push_back(x);
            v[i].push_back(y);
        }
        Dfs(1,0);
        int p=Bfs(1);
        int q=Bfs(p);
        for(int i=1;i<=n;i++)printf("%lld\n",max(Lca(p,i),Lca(q,i)));
    }
    return 0;
}