利用树的重心这一性质

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int N = 1e6 + 10;
void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int ans1=INT_MAX,ans2=0;
    vector<int> sz(n);
    auto dfs = [&](auto &&dfs, int u, int fa) -> void
    {
        sz[u] = 1;
        int mxchd=0;
        for (int i = 0; i < adj[u].size(); i++)
        {
            int nu = adj[u][i];
            if (nu != fa)
            {
                dfs(dfs, nu, u);
               sz[u]+=sz[nu];
               mxchd=max(mxchd,sz[nu]);
            }
        }
        int wt=max(n-sz[u],mxchd);
        if(wt<=n/2)
        {
            ans1=min(u,ans1);
            ans2=wt;
        }
    };
    dfs(dfs, 0, 0);
    cout<<ans1+1<<' '<<ans2<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}