直径定义：树上的最长路径，不妨设端点分别为s，t
可以证明（感觉）：每个点到其最远点必定为s or t，反之亦然
首先，第一次dfs找到s
然后，第二次dfs以s为根找到t
最后，第三次dfs以t为根
比较二三两次的当前点深度可得到答案
1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <queue> 5 #include <vector> 6 #include <cstdio> 7 #include <cstdlib> 8 #include <cstring> 9 #include <iostream> 10 #include <algorithm> 11 using namespace std; 12 const int MAXN=10010,MAXM=20010; 13 struct edge{ 14 int u,v,w,next; 15 edge(int u=0,int v=0,int w=0,int next=0):u(u),v(v),w(w),next(next){} 16 }; 17 18 edge E[MAXM]; 19 int head[MAXN],fa[MAXN],dis[MAXN],ans[MAXN],cnt,n,s,t,maxdis; 20 void add(int u,int v,int w){ 21 E[++cnt]=edge(u,v,w,head[u]),head[u]=cnt; 22 E[++cnt]=edge(v,u,w,head[v]),head[v]=cnt; 23 } 24 25 int dfs(int x,int fa){ 26 for(int i=head[x];i;i=E[i].next) 27 if(E[i].v!=fa){ 28 dis[E[i].v]=max(dis[x]+E[i].w,dis[E[i].v]); 29 dfs(E[i].v,x); 30 } 31 } 32 33 int search(int root){ 34 int x=root; 35 maxdis=0,memset(dis,0,sizeof(dis)),dfs(root,root); 36 for(int i=1;i<=n;i++)if(dis[i]>maxdis)maxdis=dis[i],x=i; 37 return x; 38 } 39 40 int main(){ 41 while(scanf("%d",&n)!=EOF){ 42 cnt=0; 43 memset(head,0,sizeof(head)); 44 for(int u=2,v,w;u<=n;u++)scanf("%d%d",&v,&w),add(u,v,w); 45 int s=search(1); 46 int t=search(s); 47 for(int i=1;i<=n;i++)ans[i]=dis[i]; 48 search(t); 49 for(int i=1;i<=n;i++)printf("%d ",max(ans[i],dis[i])); 50 } 51 return 0; 52 }