原題地址：點我跳轉
Computer
Time Limit: 1000/1000 MS (java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6551 Accepted Submission(s): 3299PRoblem DescriptionA 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.InputInput 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.OutputFor each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).Sample Input51 12 13 11 1Sample Output32344題目的大意是，給你一棵樹，求每個節點的最遠的距離。我們把最開始的點作為根節點（電腦1），建立有根樹。先用深搜遍歷一遍樹，求出對于每個父節點，其最遠的子葉子節點的最遠距離（下文簡稱為最遠子距離maxs[i]）和不同路徑的其他子葉子節點的次遠距離。
如上圖，1的最遠子葉子節點的距離是1-2-5-6 ，是5。不同路徑上的次遠子距離（下文簡稱為次遠子距離sec[i]）是1-3，是3。而不是1-2-4 ，因為節點2有重復。深搜最遠距離和次遠距離的同時，記錄好最遠距離的直接子節點編號。第二遍深搜，我們進行DP，求出答案。思路如下：每次進行dp時，以當前搜索到的點為界，將這棵樹分為兩部分，如下圖：![]()
以6號點為例，節點6的最遠距離，要么是節點6最遠子距離（6-9）maxs[6]，要么是紅圈部分的樹上節點3的最遠距離加上節點3到節點6的距離（5-2-1-3-6）+dist（3,6）（下文簡稱這個距離為局部最遠距離dp[i]）因此我們需要求得所有節點的局部最遠距離dp[i]。局部最遠距離dp[i]，可以由父節點的局部最遠距離推導。設父節點為par，子節點為son。①如果son不是par的最遠子距離上的點，例如上圖的4和3。3的最遠子距離maxs[3] = 6（3-6-9）,節點4不在上面dp[son] = dist（par, son）+ max（maxs[par], dp[par]）②如果son是par的最遠子距離上的點，例如上圖的6和3。3的最遠子距離maxs[3] = 6（3-6-9）,節點6在上面dp[son] = dist（par, son）+ max（sec[par], dp[par]）而最后的答案，就是max（dp[i], maxs[i]）AC代碼：#include<cstdio>#include<cstdlib>#include <algorithm>#include<cmath>using namespace std;struct node{ int dp;//局部最遠距離 int ans;//最后答案 int maxs;//最遠子距離 int sec;//次遠子距離 int len;//該節點到父節點的距離dist（son，par） int son;//孩子 int maxson;//最遠子距離的直接孩子 int bro;//兄弟} tree[10010];void dfs(int root)//深搜最遠子距離和次遠子距離{ if(tree[root].son==0) return; else { int p; p=tree[root].son; dfs(p); if(tree[root].maxs<tree[p].len+tree[p].maxs) { tree[root].sec = tree[root].maxs; tree[root].maxs = tree[p].len+tree[p].maxs; tree[root].maxson = p; } else if(tree[root].sec<tree[p].len+tree[p].maxs) { tree[root].sec = tree[p].len+tree[p].maxs; } //printf("!root=%d maxs=%d maxson=%d sec=%d/n",root,tree[root].maxs,tree[root].maxson,tree[root].sec); while(tree[p].bro!=0) { int tmp=p; p=tree[p].bro; dfs(p); if(tree[root].maxs<tree[p].len+tree[p].maxs) { tree[root].sec = tree[root].maxs; tree[root].maxs = tree[p].len+tree[p].maxs; tree[root].maxson = p; } else if(tree[root].sec<tree[p].len+tree[p].maxs) { tree[root].sec = tree[p].len+tree[p].maxs; } //printf("root=%d maxs=%d maxson=%d sec=%d/n",root,tree[root].maxs,tree[root].maxson,tree[root].sec); } } return;}void dfsAns(int son,int par)//深搜+DP{ if(son==1) { tree[son].dp = 0; tree[son].ans = tree[son].maxs; } else { int maxlen = tree[par].maxs; if(tree[par].maxson==son) { maxlen = tree[par].sec; } maxlen = max(tree[par].dp,maxlen); tree[son].dp = maxlen + tree[son].len; tree[son].ans = max(tree[son].dp,tree[son].maxs); } if(tree[son].son==0) return ; else dfsAns(tree[son].son,son); int p = tree[son].son; while(tree[p].bro!=0) { p = tree[p].bro; dfsAns(p,son); }}int main(){ int n; int f,l; while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) { tree[i].dp=0; tree[i].ans=0; tree[i].maxs=0; tree[i].sec=0; tree[i].son=0; tree[i].maxson=0; tree[i].bro=0; } int p; for(int i=2; i<=n; i++)//左孩子右兄弟建樹 { scanf("%d%d",&f,&l); if(tree[f].son==0) tree[f].son=i; else { p=tree[f].son; while(tree[p].bro!=0) { p=tree[p].bro; } tree[p].bro=i; } tree[i].len=l; } dfs(1); dfsAns(1,0); for(int i=1; i<=n; i++) { printf("%d/n",tree[i].ans); } } return 0;}/*//題解中的例子的數據91 11 23 32 23 43 16 26 3*/
