http://acm.hdu.edu.cn/showproblem.php?pid=2196
题意：
给你一棵树，求所有顶点到其它顶点的最大距离
树形DP
先求每个点到以它为根的子树的子节点的最大距离和次大距离（防止求它到父节点的最大距离中包含了它）
然后求它到父节点的最大距离：如果到父节点的距离中包含了它，则用次大距离，否则用最大距离（这里要注意）
1 #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <set> 8 #include <list> 9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 const int maxn = 10010; 23 const int maxm = 20010; 24 const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 const double INF = 1e30; 27 const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32 33 struct Edge 34 { 35 int u, v; 36 int w; 37 int next; 38 } edge[maxm]; 39 int en; 40 int head[maxn]; 41 void addsub(int u, int v, int w) 42 { 43 edge[en].u = u; 44 edge[en].v = v; 45 edge[en].w = w; 46 edge[en].next = head[u]; 47 head[u] = en++; 48 } 49 void add(int u, int v, int w) 50 { 51 addsub(u, v, w); 52 addsub(v, u, w); 53 } 54 int n; 55 bool vis[maxn]; 56 int dp[maxn]; 57 struct Node 58 { 59 int len; 60 int id; 61 }; 62 Node fir[maxn], sec[maxn]; 63 void init() 64 { 65 memset(head, -1, sizeof(head)); 66 en = 0; 67 memset(dp, 0, sizeof(dp)); 68 for (int i = 1; i <= n; i++) 69 { 70 fir[i].len = fir[i].id = 0; 71 sec[i].len = sec[i].id = 0; 72 } 73 } 74 void input() 75 { 76 for (int u = 2; u <= n; u++) 77 { 78 int v, w; 79 scanf("%d%d", &v, &w); 80 add(u, v, w); 81 } 82 } 83 void dfs1(int u, int p) 84 { 85 vis[u] = 1; 86 for (int i = head[u]; i != -1; i = edge[i].next) 87 { 88 int v = edge[i].v; 89 if (v == p || vis[v]) continue; 90 dfs1(v, u); 91 if (sec[u].len < fir[v].len + edge[i].w) 92 { 93 sec[u].len = fir[v].len + edge[i].w; 94 sec[u].id = v; 95 if (fir[u].len < sec[u].len) swap(fir[u], sec[u]); 96 } 97 } 98 } 99 void dfs2(int u, int p) 100 { 101 vis[u] = 1; 102 for (int i = head[u]; i != -1; i = edge[i].next) 103 { 104 int v = edge[i].v; 105 if (v == p || vis[v]) continue; 106 if (v == fir[u].id) 107 { 108 if (sec[v].len < sec[u].len + edge[i].w) 109 { 110 sec[v].len = sec[u].len + edge[i].w; 111 sec[v].id = u; 112 if (fir[v].len < sec[v].len) swap(fir[v], sec[v]); 113 } 114 } 115 else 116 { 117 if (sec[v].len < fir[u].len + edge[i].w) 118 { 119 sec[v].len = fir[u].len + edge[i].w; 120 sec[v].id = u; 121 if (fir[v].len < sec[v].len) swap(fir[v], sec[v]); 122 } 123 } 124 dfs2(v, u); 125 } 126 } 127 void debug() 128 { 129 // 130 } 131 void solve() 132 { 133 memset(vis, 0, sizeof(vis)); 134 dfs1(1, -1); 135 memset(vis, 0, sizeof(vis)); 136 dfs2(1, -1); 137 } 138 void output() 139 { 140 for (int i = 1; i <= n; i++ ) 141 { 142 printf("%d ", fir[i].len); 143 } 144 } 145 int main() 146 { 147 // std::ios_base::sync_with_stdio(false); 148 #ifndef ONLINE_JUDGE 149 freopen("in.cpp", "r", stdin); 150 #endif 151 152 while (~scanf("%d", &n)) 153 { 154 init(); 155 input(); 156 // puts("!1111"); 157 solve(); 158 output(); 159 } 160 return 0; 161 }