HDU 2136：Computer（树形DP）

http://acm.split.hdu.edu.cn/showproblem.php?pid=2196

Computer

Description

A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.

Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.

Input

Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.

Output

For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).

Sample Input

Sample Output

3
2
3
4
4

题意：给出一棵树，求树中每个节点到树中任意其他节点的最大距离。
思路：想了挺久还是不会做，只能学习一下别人的了。http://blog.csdn.net/shuangde800/article/details/9732825
　　   和之前那道水题完全天壤之别。
　　　用两次dfs来求出最大的距离。第一次dfs是求出节点i的子树节点到i的最大距离，用dp[i][0]表示（从上往下）。第二次dfs是求出不在节点i的子树的节点中的其他节点到节点i的最大距离（从下往上），即到父节点的最大距离 + 父节点和该节点的w（父节点的最大距离的路径不能包含i，若包含要用次大距离），用dp[i][1]表示。答案就取max(dp[i][0], dp[i][1]).

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <string>
  6 #include <cmath>
  7 #include <queue>
  8 #include <vector>
  9 using namespace std;
 10 #define N 10010
 11 struct node
 12 {
 13     int v, nxt, w;
 14 }edge[N*2];
 15 int head[N], tot;
 16 int dp[N][2];
 17 bool vis[N];
 18 
 19 /*
 20 dp[i][0],表示顶点为i的子树的，距顶点i的最长距离
 21 dp[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离
 22 Tree(x)表示以x为根的子树
 23 */
 24 void add(int u, int v, int w)
 25 {
 26     edge[tot].v = v;
 27     edge[tot].w = w;
 28     edge[tot].nxt = head[u];
 29     head[u] = tot++;
 30     edge[tot].v = u;
 31     edge[tot].w = w;
 32     edge[tot].nxt = head[v];
 33     head[v] = tot++;
 34 }
 35 
 36 void dfs1(int u) //回溯的时候找到各个节点子树距节点的最大距离
 37 {
 38     vis[u] = 1;
 39     for(int i = head[u]; ~i; i = edge[i].nxt) {
 40         int v = edge[i].v, w = edge[i].w;
 41         if(vis[v]) continue;
 42         dfs1(v);
 43         dp[u][0] = max(dp[u][0], w + dp[v][0]);
 44     }
 45 }
 46 
 47 void dfs2(int u) //从上往下找不属于该节点子树的节点到该节点的最大距离,即从另一个方向找
 48 {
 49     vis[u] = 1;
 50     int ma1 = 0, ma2 = 0, tmp, v1, v2;
 51     for(int i = head[u]; ~i; i = edge[i].nxt) {    //从子节点到该节点父节点最大距离
 52         int v = edge[i].v, w = edge[i].w;
 53         if(vis[v]) continue;
 54         tmp = dp[v][0] + w;
 55         if(tmp > ma1) {
 56             ma2 = ma1, v2 = v1, ma1 = tmp, v1 = v;
 57         } else if(tmp > ma2) {
 58             ma2 = tmp, v2 = v;
 59         }
 60     }
 61 
 62     if(u != 1) {  //有父节点有兄弟的话,找从其他节点到父节点的最长距离
 63         tmp = dp[u][1];
 64         int v = 0;    //这个时候一定是用dp[u][1],所以不受限制
 65         if(tmp > ma1) {
 66             ma2 = ma1, v2 = v1, ma1 = tmp, v1 = v;
 67         } else if(tmp > ma2) {
 68             ma2 = tmp, v2 = v;
 69         }
 70     }
 71 
 72     for(int i = head[u]; ~i; i = edge[i].nxt) {
 73         int v = edge[i].v, w = edge[i].w;
 74         if(vis[v]) continue;
 75         if(v == v1) {    //如果最长的距离的路径经过该节点,那么只能选次大的
 76             dp[v][1] = ma2 + w;
 77         } else {    //否则可以选最大的
 78             dp[v][1] = ma1 + w;
 79         }
 80         dfs2(v);
 81     }
 82 }
 83 
 84 int main()
 85 {
 86     int n;
 87        while(~scanf("%d", &n)) {
 88            memset(head, -1, sizeof(head));
 89            tot = 0;
 90            for(int i = 2; i <= n; i++) {
 91                int v, w;
 92                scanf("%d%d", &v, &w);
 93                add(i, v, w);
 94            }
 95 
 96            memset(vis, 0, sizeof(vis));
 97            memset(dp, 0, sizeof(dp));
 98            dfs1(1);
 99            memset(vis, 0, sizeof(vis));
100            dfs2(1);
101 
102            for(int i = 1; i <= n; i++) {
103                printf("%d
", max(dp[i][0], dp[i][1]));
104            }
105        }
106 
107     return 0;
108 }