摘要：
传送门假设数据再大些，我这就是正解，然而题解里总是各种水过。两边dfs，一遍求重心，一遍统计距离。
假设数据再大些，我这就是正解，然而题解里总是各种水过。
两边dfs，一遍求重心，一遍统计距离。
——代码
![[luoguP1364] 医院设置（树的重心）第1张](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
![[luoguP1364] 医院设置（树的重心）第2张](https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)
1 #include <cstdio> 2 #include <cstring> 3 #define MAXN 1001 4 5 using namespacestd; 6 7 intn, cnt, tot, ans, sum; 8 inthead[MAXN], next[MAXN], to[MAXN], val[MAXN], size[MAXN], dis[MAXN], f[MAXN]; 9 10 inline void add(int x, inty) 11 { 12 to[cnt] =y; 13 next[cnt] =head[x]; 14 head[x] = cnt++; 15 } 16 17 inline void dfs(intu) 18 { 19 inti, v; 20 size[u] +=val[u]; 21 for(i = head[u]; i != -1; i =next[i]) 22 { 23 v =to[i]; 24 if(v !=f[u]) 25 { 26 f[v] =u; 27 dfs(v); 28 size[u] +=size[v]; 29 } 30 } 31 if(2 * size[u] >= tot && !ans) ans =u; 32 } 33 34 inline void dfs1(intu) 35 { 36 inti, v; 37 sum += (dis[u] - 1) *val[u]; 38 for(i = head[u]; i != -1; i =next[i]) 39 { 40 v =to[i]; 41 if(!dis[v]) 42 { 43 dis[v] = dis[u] + 1; 44 dfs1(v); 45 } 46 } 47 } 48 49 intmain() 50 { 51 inti, x, y; 52 scanf("%d", &n); 53 memset(head, -1, sizeof(head)); 54 for(i = 1; i <= n; i++) 55 { 56 scanf("%d %d %d", &val[i], &x, &y); 57 if(x) add(i, x), add(x, i); 58 if(y) add(i, y), add(y, i); 59 tot +=val[i]; 60 } 61 dfs(1); 62 dis[ans] = 1; 63 dfs1(ans); 64 printf("%d", sum); 65 return 0; 66 }