Computer
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 38417 Accepted Submission(s): 6957
Problem 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
5 1 1 2 1 3 1 1 1
Sample Output
3 2 3 4 4
Author
scnu
Recommend
lcy
1 /************************************************************************* 2 > File Name: computer.cpp 3 > Author: CruelKing 4 > Mail: 2016586625@qq.com 5 > Created Time: 2019年09月23日 星期一 14时08分02秒 6 我的思路:先求出直径的两个端点,接着求出所有顶点到两个端点的距离,取其中最大的即是答案. 7 第二种思路:一个顶点距离其他顶点的最远距离要么经过儿子结点,要么经过父亲结点,那么我们就都求出来取其大就可以了. 8 需要注意的是,如果说一个说父亲的最远距离经过儿子的最远距离的话,儿子需要换一条路次短路. 9 ************************************************************************/ 10 11 #include12 #include 13 #include 14 using namespace std; 15 16 const int maxn = 10000 + 5; 17 struct Edge { 18 int to, cost, next; 19 } edge[maxn << 1]; 20 21 int n, ans; 22 23 int head[maxn], tot; 24 //int dp[maxn];//某棵树子树的大小 # TODO:这是用树的直径的时候保存的状态 25 26 int dp[maxn][3];//用dp[i][0]表示i的子树的最远距离,dp[i][1]表示i的子树的次远距离 27 //dp[i][2]表示i的祖先的最远距离,所以答案取max(dp[i][0], dp[i][2]) 28 29 void init() { 30 memset(head, -1, sizeof head); 31 tot = 0; 32 } 33 34 void addedge(int u, int v, int w) { 35 edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cost = w; head[u] = tot ++; 36 edge[tot].to = u; edge[tot].next = head[v]; edge[tot].cost = w; head[v] = tot ++; 37 } 38 39 /* 40 void dfs(int u, int pre) { 41 //TODO:求解树的直径 42 //本题没用到该函数 43 for(int i = head[u]; ~i; i = edge[i].next) { 44 int v = edge[i].to; 45 if(v == pre) continue; 46 dfs(v, u); 47 if(ans < dp[u] + dp[v] + edge[i].cost) { 48 ans = dp[u] + dp[v] + edge[i].cost; 49 } 50 if(dp[v] + edge[i].cost > dp[u]) { 51 dp[u] = edge[i].cost + dp[v]; 52 } 53 } 54 } 55 */ 56 57 /* 58 int d, M; 59 int A, B; 60 61 int dist[maxn]; 62 63 void dfs(int u, int pre, bool flag) { 64 //TODO:递归寻找树的直径的端点 65 if(d > M) { 66 M = d; 67 if(flag) 68 A = u; 69 else 70 B = u; 71 } 72 for(int i = head[u]; ~i; i = edge[i].next) { 73 int v = edge[i].to; 74 if(pre == v) continue; 75 d += edge[i].cost; 76 if(!flag) dist[v] = d; 77 dfs(v, u, flag); 78 d -= edge[i].cost; 79 } 80 } 81 82 void dfs1(int u, int pre) { 83 //TODO;寻找每个点距离两个端点的最大值 84 for(int i = head[u]; ~i; i = edge[i].next) { 85 int v = edge[i].to; 86 if(pre == v) continue; 87 d += edge[i].cost; 88 dist[v] = max(d, dist[v]); 89 dfs1(v, u); 90 d -= edge[i].cost; 91 } 92 } 93 */ 94 95 void dfs(int u, int pre) { 96 for(int i = head[u]; ~i; i = edge[i].next) { 97 int v = edge[i].to; 98 if(v == pre) continue; 99 dfs(v, u);100 int temp = 0;101 if(dp[u][0] <= dp[v][0] + edge[i].cost) {102 dp[u][1] = dp[u][0];103 dp[u][0] = dp[v][0] + edge[i].cost;104 } else if(dp[u][1] < dp[v][0] + edge[i].cost) {105 dp[u][1] = edge[i].cost + dp[v][0];106 }107 }108 // printf("%d %d %d\n", u, dp[u][0], dp[u][1]);109 }110 111 void dfs1(int u, int pre) {112 for(int i = head[u]; ~i; i = edge[i].next) {113 int v = edge[i].to;114 if(v == pre) continue;115 dp[v][2] = max(dp[u][2], dp[v][0] + edge[i].cost == dp[u][0] ? dp[u][1] : dp[u][0]) + edge[i].cost;116 dfs1(v, u);117 }118 }119 120 int main() {121 int v, w;122 while(~scanf("%d", &n)) {123 ans = 0;124 init();125 memset(dp, 0, sizeof dp);126 for(int i = 2; i <= n; i ++) {127 scanf("%d %d", &v, &w);128 addedge(i, v, w);129 }130 /*TODO:利用树的直径求解本题131 memset(dist, 0, sizeof dist);132 d = M = 0;133 dfs(1, -1, true);134 M = 0;135 dfs(A, -1, false);136 // for(int i = 1; i <= n; i ++) {137 // printf("%d\n", dist[i]);138 // }139 dfs1(B, -1);140 for(int i = 1; i <= n; i ++) {141 printf("%d\n", dist[i]);142 }143 */144 //TODO:利用树形dp求解本题145 dfs(1, -1);146 dfs1(1, -1);147 for(int i = 1; i <= n; i ++) {148 printf("%d\n", max(dp[i][0], dp[i][2]));149 }150 }151 return 0;152 }