题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2196
给一棵树，求树上各点到某点的距离中最长的距离。注意每个点都要求。
和普通求树的直径不一样，要求每一个点，点的数量是10000因此每一个点都跑一次dfs就会超时。因此先随便dfs一个点，找到一个点后以此点为原点再找距离它最远的点，再找一次即可找到树直径两端的点。
1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include <fstream> 8 #include <cassert> 9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19 20 using namespace std; 21 22 typedef struct Edge { 23 int v, w; 24 int next; 25 }Edge; 26 const int maxn = 10010; 27 int n, ecnt; 28 int head[maxn]; 29 Edge e[maxn*maxn]; 30 int dp[maxn]; 31 int ed, lp; 32 33 void init() { 34 memset(head, -1, sizeof(head)); 35 ecnt = 0; 36 } 37 38 void adde(int u, int v, int w) { 39 e[ecnt].v = v; 40 e[ecnt].w = w; 41 e[ecnt].next = head[u]; 42 head[u] = ecnt++; 43 } 44 45 void dfs(int u, int pre, int len) { 46 if(len > lp) { 47 lp = len; 48 ed = u; 49 } 50 for(int i = head[u]; ~i; i=e[i].next) { 51 if(e[i].v == pre) continue; 52 dfs(e[i].v, u, len + e[i].w); 53 dp[e[i].v] = max(dp[e[i].v], len+e[i].w); 54 } 55 } 56 57 int main() { 58 // freopen("in", "r", stdin); 59 int v, w; 60 while(~scanf("%d", &n)) { 61 init(); 62 for(int i = 2; i <= n; i++) { 63 scanf("%d %d", &v, &w); 64 adde(i, v, w); 65 adde(v, i, w); 66 } 67 lp = -1; 68 memset(dp, 0, sizeof(dp)); 69 dfs(1, -1, 0); 70 dfs(ed, -1, 0); 71 dfs(ed, -1, 0); 72 for(int i = 1; i <= n; i++) { 73 printf("%d ", dp[i]); 74 } 75 } 76 return 0; 77 }