Problem

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10010;
int dis[maxn], ans[maxn];
vector<int> G[maxn];
vector<int> L[maxn];
int n, s, t;

void _dfs(int v) {
for(int i = 0; i < G[v].size(); ++i){
if(!dis[G[v][i]]) {
dis[G[v][i]] = dis[v] + L[v][i];
_dfs(G[v][i]);
}
}
}

void _finds() {
memset(dis, 0, sizeof(dis));
s = 1; dis[s] = 1; _dfs(s);
for(int i = 2; i <= n; ++i)
if(dis[i] > dis[s]) s = i;

}

void _findt() {
memset(dis, 0, sizeof(dis));
dis[s] = 1; _dfs(s); t = 1;
for(int i = 2; i <= n; ++i)
if(dis[i] > dis[t]) t = i;
for(int i = 1; i <= n; ++i)
ans[i] = dis[i] - 1;
}

void _tdis() {
memset(dis, 0, sizeof(dis));
dis[t] = 1; _dfs(t);
for(int i = 1; i <= n; ++i)
if(dis[i] - 1 > ans[i])
ans[i] = dis[i] - 1;
}

int main() {
int i, j, k, u, v;
while(~scanf("%d", &n)){
for(i = 1; i <= n; ++i) {
G[i].clear();
L[i].clear();
}
for(i = 2; i <= n; ++i){
scanf("%d%d", &u, &v);
G[i].push_back(u);
L[u].push_back(v);
G[u].push_back(i);
L[i].push_back(v);
}
_finds();
_findt();
_tdis();
for(i = 1; i <= n; ++i)
printf("%d\n", ans[i]);
}
return 0;
}

Reference

Record

  • 2018年08月23日 完成题解