求点到其最远点的距离,用两个数组,记录一下最大值以及次大值就好了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define gc getchar()
using namespace std;
const int N=1e4+5;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,d,next;}a[N];int len,last[N];
void ins(int x,int y,int d){a[++len]=(edge){y,d,last[x]};last[x]=len;}
int w1[N],w2[N];
void dfs(int x)
{
    w1[x]=0;
    for(int k=last[x];k;k=a[k].next)//子树的最大值
    {
        int y=a[k].y;
        dfs(y);
        w1[x]=max(w1[x],w1[y]+a[k].d);
    }
}
void treedp(int x)
{
    int fs=0,ms=0,id1=-1,id2=-1;
    for(int k=last[x];k;k=a[k].next)//全局除子树的最大值
    {
        int y=a[k].y;
        if(fs<w1[y]+a[k].d)ms=fs,id2=id1,fs=w1[y]+a[k].d,id1=y;
        else if(fs==w1[y]+a[k].d)ms=fs,id2=y;
        else if(ms<w1[y]+a[k].d)ms=w1[y]+a[k].d,id2=y;
    }
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(id1!=y)w2[y]=max(w2[x]+a[k].d,fs+a[k].d);
        else w2[y]=max(w2[x]+a[k].d,ms+a[k].d);
        treedp(y);
    }
}
int main()
{
    int n;
    //freopen("d.in","r",stdin);
    //freopen("d.out","w",stdout);
    while(scanf("%d",&n)!=EOF)
    {
        len=0;memset(last,0,sizeof(last));
        //memset(w1,0,sizeof(w1));memset(w2,0,sizeof(w2));
        for(int i=1;i<n;i++){int x,d;qr(x),qr(d);ins(x,i+1,d);}
        dfs(1);w2[1]=0;
        treedp(1);
        for(int i=1;i<=n;i++)qw(max(w1[i],w2[i])),puts("");
    }
    return 0;
}