题目链接：
题目描述：
给出一个树，求删除一个节点后形成的森林中，包含节点最多的子树最少包含几个节点？
解题思路：
就是求树的重心，套用模板就可以了。
重心定义：在树中删除一个节点形成的森林后，包含节点最多的子树中节点最少，那么这个删除的节点叫做重心。
重心性质：点击可见
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 20010; 7 const int INF = 0x3f3f3f3f; 8 struct node 9 { 10 int to, next; 11 } edge[maxn * 2]; 12 int head[maxn], vis[maxn], son[maxn]; 13 int tot, ans, num, n; 14 void init () 15 { 16 tot = 0; 17 num = INF; 18 memset (head, -1, sizeof(head)); 19 memset (vis, 0, sizeof(vis)); 20 memset (son, 0, sizeof(son)); 21 } 22 void Add (int from, int to) 23 { 24 edge[tot].to = to; 25 edge[tot].next = head[from]; 26 head[from] = tot ++; 27 } 28 void dfs (int u) 29 { 30 vis[u] = 1; 31 int nu = 0; 32 for (int i=head[u]; i!=-1; i=edge[i].next) 33 { 34 int v = edge[i].to; 35 if (!vis[v]) 36 { 37 dfs (v); 38 son[u] += son[v] + 1;//u的子节点数目 39 nu = max (nu , son[v] + 1);//u的子树最大的节点数目 40 } 41 42 } 43 nu = max (nu, n-son[u]-1);//(u子树最大节点数目,u点向上的节点数目) 44 if (nu<num || num==nu && ans>u) 45 { 46 num = nu; 47 ans = u; 48 } 49 } 50 int main () 51 { 52 int t; 53 scanf ("%d", &t); 54 while (t --) 55 { 56 init (); 57 scanf ("%d", &n); 58 for (int i=1; i<n; i++) 59 { 60 int u, v; 61 scanf ("%d %d", &u, &v); 62 Add (u, v); 63 Add (v, u); 64 } 65 dfs (1); 66 printf ("%d %d ", ans, num); 67 } 68 return 0; 69 }