题解 | #小G有一个大树#

#include <iostream> 
#include <cstring>

using namespace std;

const int N = 1010;

int n;
int h[N], e[N], ne[N], idx;
int si[N];//每个节点对应的子树大小
int mi = 1e9, id;//mi表示最大子树中的最小子树 id表示重心编号

void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}

//求出每个节点对应的子树大小和父子关系
int dfs(int x, int f)
{
    si[x] = 1;
    int ma = -1e9;//x的所有子树中最大子树的节点个数
    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != f) 
        {
            int s = dfs(j, x);
            si[x] += s;
            ma = max(ma, s);
        }
    }
    
    //n-si[x]表示整棵树去掉以x为根的子树后剩余的树的节点个数
    int k = max(n - si[x], ma);
    if (mi > k) mi = k, id = x;
    else if (mi == k && id > x) id = x;
    
    return si[x];   
}

int main() 
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i ++)
    {
        int x, y; cin >> x >> y;
        add(x, y), add(y, x);
    }
    
    //以任意一个点为根，求出每个节点对应的子树大小和父子关系
    dfs(1, 0);
    cout << id << ' ' << mi;

    return 0;
}