Initiate

  134. Centroid

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

You are given an undirected connected graph, with N vertices and N-1 edges (a tree). You must find the centroid(s) of the tree.
In order to define the centroid, some integer value will be assosciated to every vertex. Let's consider the vertex k. If we remove the vertex k from the tree (along with its adjacent edges), the remaining graph will have only N-1 vertices and may be composed of more than one connected components. Each of these components is (obviously) a tree. The value associated to vertex k is the largest number of vertices contained by some connected component in the remaining graph, after the removal of vertex k. All the vertices for which the associated value is minimum are considered centroids.

The first line of the input contains the integer number N (1<=N<=16 000). The next N-1 lines will contain two integers, a and b, separated by blanks, meaning that there exists an edge between vertex a and vertex b.

You should print two lines. The first line should contain the minimum value associated to the centroid(s) and the number of centroids. The second line should contain the list of vertices which are centroids, sorted in ascending order.

Sample Input

7
1 2
2 3
2 4
1 5
5 6
6 7

Sample Output

3 1
1

给一棵n个节点的树，求这棵树的重心。
树的重心就是是指删掉它以后，
剩下的最大的连通子树的节点数是最少的点。

因为树是保证连通的，所以从任何一个节点都可以把这棵树拎起来。

所以可以从任何一个点去DFS（返回子节点个数+1）

#include<iostream>
#include<algorithm>
#include<vector>
#define pk(x) push_back(x)
using namespace std;
const int N=16010;
vector<int>g[N]; 
int n,value=0x7fffffff,num;//n为边数，value为最小权值，num为重心个数 
int res[N],vis[N];
int dfs(int u)//
{
    vis[u]=1;
    int sum=0,k=0,tmp;//k是节点u的value.Sum是u的所有子节点的个数 
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(!vis[v]){
            tmp=dfs(v);
            sum += tmp;
            if(k<tmp) k=tmp;//k(f[u])=max{sum[v]+1}sum[v]是v的所有子节点个数+v自己 
            }
        }
    tmp=n-1-sum;//k(f[u])=max{k,n-1-sum}//将该节点和该节点的所有子节点划去的剩余部分 
    if(k<tmp) k=tmp;
    if(value>k){//求所有节点中最小的权值 
        value=k;
        num=1;//发现更小的，置num为1 
        res[1]=u;
    }
    else if(value==k){
        res[++num]=u;
    }
    return sum+1;
    }
int main()
{
    scanf("%d",&n);
    int i,a,b;
    for(i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        g[a].pk(b);
        g[b].pk(a);
    }
    dfs(1);
    printf("%d %d\n",value,num);
    sort(res+1,res+num+1);
    if(num>0) 
        printf("%d",res[1]);
    for(i=2;i<=num;i++)
        printf(" %d",res[i]);
    printf("\n");
}