2010年02月28日星期日.sgu149
sgu149:tree dp
这个题想了好久，第一遍代码写的太乱了，然后就重新写了一遍，还好过了。。
思路就是每个点的最长距离有两个来源，一个是子节点，一个是父节点。
字节点的即是深度，这个好求。
如果是来自父节点，那么假定父节点的最长距离已经获得，
如果这个最长距离不是来自当前节点，就可一直接加上父节点到这个节点的边长。
如果这个最长距离恰好来自这个节点，那么可以使用父节点不来自这个节点的最长路来做同样的事情。
1
2 #define pb(x) push_back(x)
3 const int N = 10100;
4 vector<int> g[N];
5 int deep[N],n,far1[N],far2[N],branch[N],vis[N];
6 int out[N];
7
8 void dfs1(int u)
9 {
10 vis[u] = true;
11 int res = 0,idx = 0;
12 for (int i = 0;i < g[u].size();i +=2 ) {
13 int v = g[u][i];
14 int w = g[u][i+1];
15 if (!vis[v]) {
16 dfs1(v);
17 if (res < deep[v] + w) {
18 res = deep[v] + w;
19 idx = v;
20 }
21 }
22 }
23 deep[u] = res;
24 }
25
26 void dfs2(int u,int cost) // u is current // cost from parent
27 {
28 vis[u] = true;
29 branch[u] = 0;
30 far1[u] = cost;
31 far2[u] = 0;
32
33 int i,sz = g[u].size();
34 for (i = 0;i < sz;i += 2) {
35 int v = g[u][i];
36 int w = g[u][i+1];
37 if (vis[v]) { continue; } //!
38 if (far1[u] < deep[v] + w ) {
39 far2[u] = far1[u];
40 far1[u] = deep[v] + w ;
41 branch[u] = v;
42 }else if (far2[u] < deep[v] + w ) {
43 far2[u] = deep[v] + w;
44 }
45 }
46 //http://www.cppblog.com/schindlerlee
47 for (i = 0;i < sz;i += 2) {
48 int v = g[u][i];
49 int w = g[u][i+1];
50 if (vis[v]) { continue; }
51 if (v != branch[u]) {
52 dfs2(v,far1[u] + w);
53 }else {
54 dfs2(v,far2[u] + w);
55 }
56 }
57 }
58
59 int main()
60 {
61 int i,j,k,a,b;
62 scanf("%d",&n);
63 for (i = 2;i <= n;i++) {
64 scanf("%d%d",&a,&b);
65 g[i].pb(a),g[i].pb(b);
66 g[a].pb(i),g[a].pb(b);
67 }
68 dfs1(1);
69 memset(vis,0,sizeof(vis));
70 dfs2(1,0);
71 for ( i = 1; i <= n; i++) {
72 printf("%d\n",far1[i]);
73 }
74
75 return 0;
76 }
77