树的重心

看了网上大牛们求重心的方法，自己也写写。

假设x结点是树的重心，那么现在删除一个树的结点，就可以得到一些子树，那么得到的子树中结点个数最大的数要最小就是树的重心。（有点啰嗦）

root = min(max(son(x)))

枚举树的每个结点，计算以每个结点为根的对应的各个子树的结点的最大值，然后再取一个最小值，那个最小值对应结点的就是重心。

 1 #include <string.h>
 2 #include <algorithm>
 3 using namespace std;
 4 #define N 10000
 5 #define INF 0x7fffffff
 6 int head[N], cnt;
 7 struct node
 8 {
 9     int next, to;
10 }edge[N * 2];
11 int root, minnum, son[N];
12 void addedge(int from, int to)
13 {
14     cnt++;
15     edge[cnt].next = head[from];
16     edge[cnt].to = to;
17     head[from] = cnt;
18 }
19 void init()
20 {
21     cnt = 0;
22     minnum = INF;
23     memset(head, 0, sizeof(size));
24     //memset(son, 0, sizeof(size));
25 }
26 
27 void findroot(int x, int pre)
28 {
29     son[x] = 0;
30     int i, j;
31     int temp = 0;
32     for (i = head[x]; i; i = edge[i].next)
33     {
34         j = edge[i].to;
35         if (j != pre)
36         {
37             findroot(j, x);
38             temp = max(temp, son[j] + 1);//最大子树结点个数
39             son[x] += son[j] + 1;//所有子树结点个数    
40         }
41     }
42     temp = max(temp, n - son[x] - 1);//n为整个树的结点个数 
43     if (temp < minnum)//找到更合适的重心 
44     {
45         minnum = temp;
46         root = x;
47     }
48 }