经典换根dp——hdu2196-蒲公英云

经典换根dp——hdu2196

给定一棵边权树，求距离每个点最远的点，输出这个距离

#include<bits/stdc++.h>
using namespace std;
#define N 10005
struct Edge{
    int to,nxt,w;}e[N<<1];
int head[N],tot,n;
void init(){memset(head,-1,sizeof head);tot=0;}
void add(int u,int v,int w){
    e[tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot++;
}
int d[N];
void dfs1(int u,int pre){
    d[u]=0;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        dfs1(v,u);
        d[u]=max(d[u],d[v]+e[i].w);
    }
}
int ans[N];
void dfs2(int u,int pre,int up){
    int mx1,mx2,id1,id2;
    mx1=mx2=0;
    id1=id2=0;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        if(d[v]+e[i].w>=mx1){
            mx2=mx1,id2=id1;
            mx1=d[v]+e[i].w,id1=v;
        }
        else if(d[v]+e[i].w>=mx2)
            mx2=d[v]+e[i].w,id2=v;
    }
    if(up>=mx1){
        mx2=mx1,id2=id1;
        mx1=up,id1=0;
    }
    else if(up>=mx2)
        mx2=up,id2=0;
    ans[u]=mx1;
    for(int i=head[u];i!=-1;i=e[i].nxt){
        int v=e[i].to;
        if(v==pre)continue;
        if(v==id1)
            dfs2(v,u,mx2+e[i].w);
        else 
            dfs2(v,u,mx1+e[i].w);
    }    
}
int main(){
    while(cin>>n){
        init();
        for(int i=2;i<=n;i++){
            int v,w;
            scanf("%d%d",&v,&w);
            add(i,v,w);add(v,i,w);
        }    
        dfs1(1,1);
        dfs2(1,1,0);
        for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    }
}
/*
7 
1 10
1 20
2 2
2 1
3 1
3 100
*/