hdu 2196(树的最长链)

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 #define MP(a, b) make_pair(a, b)
14 #define PB(a) push_back(a)
15 using namespace std;
16 
17 const int LEN = 10010;
18 const int INF = 0x3f3f3f3f;
19 typedef pair<int, int> pii;
20 vector<pii> Map[LEN];
21 int n, vis[LEN], dis[LEN], disa[LEN];
22 
23 
24 int bfs(int v){
25     queue<int> q;
26     memset(vis, 0, sizeof vis);
27     memset(dis, 0, sizeof dis);
28     q.push(v);
29     vis[v] = 1;
30     while(!q.empty()){
31         int nv = q.front(); q.pop();
32         for(int i=0; i<Map[nv].size(); i++){
33             int x = Map[nv][i].first;
34             if(!vis[x]){
35                 vis[x] = 1;
36                 dis[x] = dis[nv] + Map[nv][i].second;
37                 q.push(x);
38             }
39         }
40     }
41     int maxv = -INF, maxn;
42     for(int i=0; i<n; i++){
43         if(maxv < dis[i]){
44             maxv = dis[i];
45             maxn = i;
46         }
47     }
48     return maxn;
49 }
50 
51 int main()
52 {
53  //   freopen("in.txt","r",stdin);
54  //   freopen("out.txt","w",stdout);
55     
56     int a, b;
57     while(scanf("%d", &n)!=EOF){
58         for(int i=0; i<LEN; i++) Map[i].clear();
59         for(int i=1; i<n; i++){
60             scanf("%d%d", &a, &b);
61             a--;
62             Map[i].PB(MP(a, b));
63             Map[a].PB(MP(i, b));
64         }
65         int vexa = bfs(0);
66         int vexb = bfs(vexa);
67         for(int i=0; i<n; i++)disa[i] = dis[i];
68         bfs(vexb);
69         for(int i=0; i<n; i++){
70             printf("%d\n", max(disa[i], dis[i]));
71         }
72     }
73     return 0;
74 }