给出一棵树，求出树的中心。

为了定义树的中心，首先给每个结点进行标号。对于一个结点K，如果把K从树中删除（连同与它相连的边一起），剩下的被分成了很多块，每一块显然又是一棵树（即剩下的部分构成了一个森林）。则给结点K所标的号就是森林中结点个数最多的树所拥有的结点数。如果结点K的标号不大于其他任何一个结点的标号，则结点K被称为是树的中心。

输入：

输入的第一行包含一个整数N（1≤N≤16 000），表示树中的结点数。接下来N-1行，每个两个整数a,b，由一个空格分隔，表示a与b之间有一条边。

输出：

输出两行，第一行两个整数v,T，v表示树的中心结点的标号，T表示树有多少个中心。第二行包含T个数，为所有树的中心的编号，按升序排列。

样例输入：

7

1 2

2 3

2 4

1 5

5 6

6 7

样例输出：

3 1

1

数据范围: 20% N<=100 100% N<=16 000

______________________________________________________________________________________________________

树形动归

深搜，得到每个点为根的子树的大小，n-每个子树大小得到，这其中较大值为大小，值最小的点就是重心。

_______________________________________________________________________________________________________

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn=16010;

 4 int n;

 5 struct edge

 6 {

 7     int u,v,next;

 8 }e[maxn<<1];

 9 int head[maxn],js;

10 int size[maxn],ss[maxn];

11 void addage(int u,int v)

12 {

13     e[++js].u=u;e[js].v=v;

14     e[js].next=head[u];head[u]=js;

15 }

16 void dfs(int u,int fa)

17 {

18     size[u]=1;

19     for(int i=head[u];i;i=e[i].next)

20     {

21         int v=e[i].v;

22         if(v!=fa)

23         {

24             dfs(v,u);

25             if(size[v]>ss[u])ss[u]=size[v];

26             size[u]+=size[v];

27         }

28     }

29     if(ss[u]<n-size[u])ss[u]=n-size[u];

30 }

31 int main()

32 {

33     scanf("%d",&n);

34     for(int u,v,i=1;i<n;++i)

35     {

36         scanf("%d%d",&u,&v);

37         addage(u,v);

38         addage(v,u);

39     }

40     dfs(1,0);

41     int sz=n,nn=0;

42     for(int i=1;i<=n;++i)

43     {

44         if(ss[i]<sz)

45         {

46             sz=ss[i];

47             nn=1;

48         }

49         else if(ss[i]==sz)nn++;

50     }

51     printf("%d %d\n",sz,nn);

52     for(int i =1;i<=n;++i)

53         if(ss[i]==sz)printf("%d ",i);

54     return 0;

55 }