原題：
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.
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
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.
Author
scnu
Recommend
lcy | We have carefully selected several similar problems for you: 1561 1011 3456 1520 2242
中文：
給你一棵樹，問你距離i節點最遠是多少？
代碼1：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
typedef pair<int,int> edge;
map<edge, int> weight;
int f[maxn];
int n, max_len, p;
vector<int> G[maxn];
void dfs(int cur, int pre, int len) {
if (max_len <= len) {
max_len = len;
p = cur;
}
for (int i = 0; i < G[cur].size(); i++) {
if (G[cur][i] == pre) {
continue;
}
int w = weight[make_pair(cur, G[cur][i])];
dfs(G[cur][i], cur, len + w);
f[G[cur][i]] = max(f[G[cur][i]], len + w);
}
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> n) {
for (int i=1;i<=n;i++) {
G[i].clear();
}
memset(f, 0, sizeof(f));
int a,b;
for (int i=2;i<=n; i++) {
cin >> a >> b;
G[i].push_back(a);
weight[make_pair(i,a)] = b;
G[a].push_back(i);
weight[make_pair(a,i)] = b;
}
p = max_len = 0;
dfs(1, -1, 0);
dfs(p, -1, 0);
dfs(p, -1, 0);
for (int i=1;i<=n;i++) {
cout << f[i] <<endl;
}
}
return 0;
}
/*
Sample Input
5
1 1
2 1
3 1
1 1
Sample Output
3
2
3
4
4
*/
代碼2：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
typedef pair<int,int> edge;
map<edge, int> weight;
int f1[maxn], f2[maxn], f3[maxn];
bool vis[maxn];
int max_path[maxn];
int n;
vector<int> G[maxn];
void dfs_down(int cur, int pre) {
for (int i = 0; i < G[cur].size(); i++) {
if (G[cur][i] == pre) {
continue;
}
dfs_down(G[cur][i], cur);
int w = weight[make_pair(cur, G[cur][i])];
if (f1[cur] < f1[G[cur][i]] + w) {
f2[cur] = f1[cur];
f1[cur] = f1[G[cur][i]] + w;
max_path[cur] = G[cur][i];
} else {
if (f2[cur] < f1[G[cur][i]] + w) {
f2[cur] = f1[G[cur][i]] + w;
}
}
}
}
void dfs_up(int cur, int pre) {
for (int i = 0; i< G[cur].size(); i++) {
if (G[cur][i] == pre) {
continue;
}
int w = weight[make_pair(cur, G[cur][i])];
if (max_path[cur] == G[cur][i]) {
f3[G[cur][i]] = max(f3[cur], f2[cur]) + w;
} else {
f3[G[cur][i]] = max(f3[cur], f1[cur]) + w;
}
dfs_up(G[cur][i], cur);
}
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> n) {
for (int i=1;i<=n;i++) {
G[i].clear();
}
memset(f1, 0, sizeof(f1));
memset(f2, 0, sizeof(f2));
memset(f3, 0, sizeof(f3));
memset(max_path, 0 ,sizeof(max_path));
int a,b;
for (int i=2;i<=n; i++) {
cin >> a >> b;
G[i].push_back(a);
weight[make_pair(i,a)] = b;
G[a].push_back(i);
weight[make_pair(a,i)] = b;
}
dfs_down(1, -1);
dfs_up(1, -1);
for (int i=1;i<=n;i++) {
cout << max(f1[i], f3[i]) <<endl;
}
}
return 0;
}
/*
Sample Input
5
1 1
2 1
3 1
1 1
Sample Output
3
2
3
4
4
*/
解答：
此題需要了解樹的直徑怎麼計算。
見 樹的直徑
有兩種做法，參考了網上的一篇部落格，總結的很好。
第一種做法，代碼2：
維護一個 d p [ i ] [ 3 ] dp[i][3] dp[i][3]
其中, d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示i到其葉子節點的最長距離， d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示i節點到其葉子節點的次長距離， d p [ i ] [ 2 ] dp[i][2] dp[i][2]表示i節點經過其父節點能到達的最遠距離，同時記錄節點i走哪個葉子節點能得到最長路徑，記為max_path。
那麼，求i節點到其葉子節點的最遠距離和次遠距離的方法就是計算樹的直徑的過程。
在計算i節點經過其父節點時的最遠距離，需要如下考慮：
如果節點i到其父親節點fa[i]的邊是其節點fa[i]的max_path，那麼節點i經過父親節點的最長路徑，應該是其fa[i]的次長路徑加上fa[i]到i的長度，如下圖，黑色線表示節點f最長路徑所在子節點的邊，藍色線是其次長路徑所在子節點的邊。
如果節點i到其父親節點fa[i]的邊不是節點fa[i]的max_path，那就應該讓目前fa[i]到i的路徑，加上fa[i]最長路徑的距離。
第二種做法，見代碼1：
這裡需要掌握一個結論，即在一顆樹上，任一節點所在最長路徑，必然經過這顆樹的直徑，并且終點是這棵樹直徑的端點之一。
證明：
這裡假設樹T有一條直徑，設葉子節點a和葉子節點b是樹上直徑的兩個端點，現在要找距離葉子節點i的最遠節點，假設這個葉子節點是j，如果j不等于a或者b，那麼說明存在另外一條直徑i到j比a到b要長，沖突。是以，從葉子節點出發所得到的最遠點已經是這顆樹上直徑的一個端點。
如果，要尋找的節點i不是葉子節點，那麼距離節點i的最遠點，已經是在某一點j到a或者b的路徑上，情況同上。
是以，處理方法是先從任意節點出發，找到最遠點a，再從最遠點a出發，找到距離a的最遠點b，同時記錄周遊所得到節點的最遠距離，再從b周遊，更新所到節點的最遠距離，即可得到答案。