题意：给出n-1条边，构造成一颗树，求：1~n节点最远的点的距离。
分析：
离该节点距离最远：有两条路走，（设该点为 now）
1、往自己的子节点走，遍历就可以得到最大值。
2、先往自己的父节点走，那么问题就变成了离父节点的最长距离，以此类推，就是一个dp的问题。
求离父节点的最长距离：又有两条路走：（1）往自己的子节点走，求出这个方向的最大值，但有可能这条路经过 now 那这样就不行了，和 1、这条路重复，
所以要记录次长路。（2）又往父节点走，重复子问题。
代码：
#include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> const int max_=10005; using namespace std; struct Tree{//邻接表存树 int to; int w; int next; }edge[2*max_]; int dis[max_][3];//3种距离 int head[max_]; int longest[max_];//记录最长路走的子节点 int tot; void add_edge(int form,int to,int w)//双向加边 { edge[tot].to=to; edge[tot].w=w; edge[tot].next=head[form]; head[form]=tot++; } int dfs1(int now,int fa)//求出正向的最长和次长 { if(dis[now][0]>=0)//记忆化搜索 return dis[now][0]; dis[now][0]=dis[now][1]=longest[now]=0;//归0 for(int i=head[now];i!=-1;i=edge[i].next) { int go_to=edge[i].to; if(go_to==fa) continue; int go_w=edge[i].w; if(go_w+dfs1(go_to,now)>dis[now][0])//跟新 { longest[now]=go_to; dis[now][1]=max(dis[now][0],dis[now][1]); dis[now][0]=go_w+dfs1(go_to,now); } else if(go_w+dfs1(go_to,now)>dis[now][1])//跟新次短 { dis[now][1]=go_w+dfs1(go_to,now); } } return dis[now][0]; } void dfs2(int now,int fa)//求反向的最长 { for(int i=head[now];i!=-1;i=edge[i].next) { int go_to=edge[i].to; if(go_to==fa) continue; int go_w=edge[i].w; if(longest[now]==go_to)//判断该路是否跟最长重复 dis[go_to][2]=max(dis[now][1],dis[now][2])+go_w; else dis[go_to][2]=max(dis[now][0],dis[now][2])+go_w; dfs2(go_to,now); } } void init()//初始化 { tot=0; memset(head,-1,sizeof(head)); memset(dis,-1,sizeof(dis)); memset(longest,-1,sizeof(longest)); } int main() { int n; while(~scanf("%d",&n)) { init(); if(n==0) break; for(int i=2;i<=n;i++) { int x,w; scanf("%d %d",&x,&w); add_edge(i,x,w); add_edge(x,i,w); } dfs1(1,-1); dfs2(1,-1); for(int i=1;i<=n;i++) { printf("%d ",max(dis[i][0],dis[i][2])); } } }