HDU 2196

 1 //树形DP，求树的最大直径。。。。
 2 #include<stdio.h>
 3 
 4 #include<string.h>
 5 #include<vector>
 6 using namespace std;
 7 #define Max(x,y) (x>y?x:y)
 8 #define max 10000+5
 9 
10 vector<int> next[max];//存图
11 int n,cost[max],dp[max],sec[max],up[max],f[max];
12 //dp[i] 结点i在其子树上的最大直径
13 //sec[i]结点i在其子树上的次最大直径
14 //up[i] 结点i通过其父结点可获得的最大直径
15 //f[i]  结点i在其子树上获得最大直径所通过的子结点
16 
17 
18 void init(){
19     for(int i=0;i<=n;i++){
20         next[i].clear();
21     }
22     memset(sec,0,sizeof(sec));
23     memset(f,0,sizeof(f));
24     memset(dp,0,sizeof(dp));
25     memset(up,0,sizeof(up));
26     memset(cost,0,sizeof(cost));
27 }
28 
29 int dfs(int u){
30     int pre;//记录在子树上获得最大直径所通过的子结点
31     int& res=dp[u];
32     for(int i=0;i<next[u].size();i++){
33         int v=next[u][i];
34             int temp=dfs(v)+cost[v];
35         if(res<temp){         //更新最大直径
36             sec[u]=res;   
37             res=temp; pre=v;
38         }
39         else if(temp>sec[u]){//更新次最大直径
40             sec[u]=temp;
41         }
42     }
43     f[u]=pre;
44     return res;
45 }
46 
47 void DP(int u){
48     for(int i=0;i<next[u].size();i++){
49         int v=next[u][i];
50         if(f[u]==v){    //如果结点u通过其子结点v得到最大直径
51             up[v]=Max(up[u],sec[u])+cost[v];
52         }
53         else{
54             up[v]=Max(up[u],dp[u])+cost[v];
55         }
56         DP(v);
57     }
58 }
59 
60 int main(){
61     while(~scanf("%d",&n)){
62         init();
63         for(int i=2;i<=n;i++){
64             int a,b;
65             scanf("%d%d",&a,&b);
66             next[a].push_back(i);
67             cost[i]=b;
68         }
69         dfs(1);        //计算每个结点到其子树上叶结点最大距离
70         DP(1);         //更新最大距离
71         for(int i=1;i<=n;i++){
72             printf("%d
",Max(dp[i],up[i]));//取向下和向上的最大值
73         }
74     }
75 }