Centroid - SGU 134(树的搜索)

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;

const int MAXN = 16007;

int val[MAXN], MinVal, cnt, N;
bool used[MAXN];
vector<int> G[MAXN];

int DFS(int k)
{
    int sumSon = 0;

    for(int i=0; i<G[k].size(); i++)
    {
        int v = G[k][i];
        if(!used[v])
        {
            used[v] = true;
            int son = DFS(v);
            val[k] = max(val[k], son);
            sumSon += son;
        }
    }

    val[k] = max(val[k], N-sumSon-1);
    if(MinVal > val[k])
    {
        MinVal = val[k];
        cnt = 1;
    }
    else if(MinVal == val[k])
        cnt++;

    return sumSon + 1;
}

int main()
{
    int u, v;

    scanf("%d", &N);

    for(int i=1; i<N; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    MinVal = MAXN;
    used[1] = true;
    DFS(1);

    printf("%d %d\n", MinVal, cnt);

    int flag=0;
    for(int i=1; i<=N; i++)
    {
        if(val[i] == MinVal)
        {
            if(flag++)printf(" ");
            printf("%d", i);
        }
    }
    printf("\n");

    return 0;
}