【题意】：给出一棵树，求离每个节点最远的点的距离。
【题解】：经典的树dp，两次dfs即可。
第一次dfs把无向树变成有向树，并且求出每个节点到他子孙的最远距离。 down[]
第二次dfs求出每个节点经过其父亲结点到其他点的最远距离。 up[]
最后ans[i] = max(down[i], up[i]);
rec[i][0] 记录哪个子孙到结点i的距离最大
rec[i][1] 记录哪个子孙到结点i的距离次大
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "vector"
5 using namespace std;
6 #define pb push_back
7 #define maxn 10050
8 int n;
9 int down[maxn], up[maxn];
10 int rec[maxn][2], edge[maxn];
11 struct Edge {
12 int v, w;
13 Edge(){}
14 Edge(int _v, int _w) {
15 v = _v, w = _w;
16 }
17 };
18 vector<Edge> g[maxn];
19
20 void dfs1(int u, int fa) {
21 down[u] = 0;
22 rec[u][0] = rec[u][1] = -1;
23 int size = g[u].size();
24 for(int i = 0; i < size; i++) {
25 int v = g[u][i].v, w = g[u][i].w;
26 if(v == fa) continue;
27 dfs1(v, u);
28 edge[v] = w;
29 if(down[v] + w >= down[u]) {
30 down[u] = down[v] + w;
31 rec[u][1] = rec[u][0];
32 rec[u][0] = v;
33 } else if(rec[u][1] == -1 || down[v] + w > down[rec[u][1]] + edge[rec[u][1]]) rec[u][1] = v;
34 }
35 }
36
37 void dfs2(int u, int fa) {
38 up[u] = 0;
39 if(fa != -1) {
40 if(u == rec[fa][0]) {
41 up[u] = up[fa] + edge[u];
42 if(rec[fa][1] != -1) up[u] = max(up[u], down[rec[fa][1]] + edge[rec[fa][1]] + edge[u]);
43 } else up[u] = max(up[fa], down[fa]) + edge[u];
44 }
45 int size = g[u].size();
46 for(int i = 0; i < size; i++) {
47 int v = g[u][i].v;
48 if(v == fa) continue;
49 dfs2(v, u);
50 }
51 }
52
53 int main() {
54 int v, w;
55 while(~scanf("%d", &n)) {
56 for(int i = 0; i < maxn; i++) g[i].clear();
57 for(int i = 2; i <= n; i++) {
58 scanf("%d%d", &v, &w);
59 g[i].pb(Edge(v, w));
60 g[v].pb(Edge(i, w));
61 }
62 dfs1(1, -1);
63 dfs2(1, -1);
64 for(int i = 1; i <= n; i++) printf("%d\n", max(up[i], down[i]));
65 }
66 return 0;
67 }
68