1 //Accepted    740 KB    15 ms  2 //树的直径  3 //距离一个顶点最远的点一定是树的直径的一个端点  4 #include <cstdio>  5 #include <cstring>  6 #include <queue>  7 #include <iostream>  8 using namespace std;  9 const int imax_n = 10005; 10 int dis[imax_n]; 11 int d1[imax_n]; 12 int d2[imax_n]; 13 int head[imax_n]; 14 int next[2*imax_n]; 15 int e; 16 struct node 17 { 18     int u,v,c; 19     node() 20     { 21  22     } 23     node(int u,int v,int c) 24     { 25         this->u=u; 26         this->v=v; 27         this->c=c; 28     } 29 }p[2*imax_n]; 30 int n; 31 void addEdge(int u,int v,int c) 32 { 33     p[e]=node(u,v,c); 34     next[e]=head[u]; 35     head[u]=e++; 36 } 37 void init() 38 { 39     memset(head,-1,sizeof(head)); 40     memset(next,-1,sizeof(next)); 41     e=0; 42 } 43 void read() 44 { 45     init(); 46     int x,y; 47     for (int i=2;i<=n;i++) 48     { 49         scanf("%d%d",&x,&y); 50         addEdge(i,x,y); 51         addEdge(x,i,y); 52     } 53 } 54 int max(int a,int b) 55 { 56     return a>b?a:b; 57 } 58 queue<int >q; 59 bool vis[imax_n]; 60 int bfs(int s) 61 { 62     //printf("111111\n"); 63     memset(dis,0,sizeof(dis)); 64     int ans=0; 65     int temp_node; 66     while (!q.empty()) q.pop(); 67     memset(vis,0,sizeof(vis[0])*(n+2)); 68     q.push(s); 69     vis[s]=1; 70     while (!q.empty()) 71     { 72         int x=q.front(); 73         if (dis[x]>ans) 74         { 75             ans=dis[x]; 76             temp_node=x; 77         } 78         q.pop(); 79         for (int i=head[x];i!=-1;i=next[i]) 80         { 81             int y=p[i].v; 82             if (!vis[y]) 83             { 84                 vis[y]=1; 85                 q.push(y); 86                 if (dis[x]+p[i].c>dis[y]) 87                 dis[y]=dis[x]+p[i].c; 88             } 89         } 90     } 91     return temp_node; 92 } 93 int main() 94 { 95     while (scanf("%d",&n)!=EOF) 96     { 97         read(); 98         int x=bfs(1); 99         x=bfs(x);100         memcpy(d1,dis,sizeof(dis));101         bfs(x);102         memcpy(d2,dis,sizeof(dis));103         for (int i=1;i<=n;i++)104         {105             printf("%d\n",max(d1[i],d2[i]));106         }107     }108     return 0;109 }