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

//对于某个节点来说，如果该节点删除那么就会形成他儿子节点全部独立成一棵树和他父亲节点的那棵树。
//那么状态转移方程：dp[i] = (total-f[i], (所有儿子节点最大的那个)f[u])
//对于求某个节点下有多少节点来说是一个简答树状dp问题。
//f[i] = 1+(所有儿子节点)f[i];
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1000+10;
int n;
vector<int> v[maxn];
int f[maxn];
int dp[maxn];
int ans = 0, ans_val=0x3f3f3f3f;

int dfs(int x, int fa) {
    int len = v[x].size();
    int son_max = 0;
    f[x] = 1;
    for (int i=0;i<len;i++) {
        int next = v[x][i];
        if (next == fa) continue;
        int num = dfs(next, x);
        f[x] += num;
        son_max = max(son_max, num);
    }
    int t = max(n-f[x], son_max);
    dp[x] = t;
    return f[x];
}

int main() {
    cin>>n;
    int x, y;
    memset(dp, 127, sizeof(dp));
    for (int i=1;i<n;i++) {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    for (int i=1;i<n;i++) {
        if (ans_val>dp[i]) {
            ans_val = dp[i];
            ans = i;
        }
    }
    cout<<ans<<" "<<ans_val;
    return 0;
}