思路：先求以1为根时，每个节点到子节点的最大长度。然后再次从1进入进行更新。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #define Maxn 20010 #define inf 0x7fffffff using namespace std; int vi[Maxn],si[Maxn],n,road[Maxn],Max[Maxn],lMax[Maxn],head[Maxn],e; struct Edge{ int u,v,val,next; }edge[Maxn*2]; void init() { memset(vi,0,sizeof(vi)); memset(si,0,sizeof(si)); memset(road,0,sizeof(road)); memset(Max,0,sizeof(Max)); memset(lMax,0,sizeof(lMax)); memset(head,-1,sizeof(head)); e=0; } void add(int u,int v,int val) { edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++; edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++; } int dfs(int u) { int i,v,sz; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(vi[v]) continue; int temp=dfs(v); if(temp+edge[i].val>Max[u]) { lMax[u]=Max[u]; Max[u]=temp+edge[i].val; road[u]=v; } else if(temp+edge[i].val>lMax[u]) lMax[u]=temp+edge[i].val; } return Max[u]; } void update(int u,int val) { int i,v,sz; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(vi[v]) continue; if(road[u]==v) update(v,max(val,lMax[u])+edge[i].val); else update(v,max(Max[u],val)+edge[i].val); } Max[u]=max(Max[u],val); } int main() { int i,j,a,b; while(scanf("%d",&n)!=EOF) { init(); for(i=2;i<=n;i++){ scanf("%d%d",&a,&b); add(i,a,b); } dfs(1); memset(vi,0,sizeof(vi)); update(1,0); for(i=1;i<=n;i++) printf("%d ",Max[i]); } return 0; }