Python3 解法, 执行用时: 37ms, 内存消耗: 4648K, 提交时间: 2022-07-14 19:47:24

n=int(input())
g=[[] for _ in range(n+1)]
s=[0]*(n+1)
#s[u]表示以u为根的子树大小（向下）
for _ in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
    
res,ans=10**18,10**18

def dfs1(u,fa):
    s[u]=1
    mmin=-1
    global ans,res
    for v in g[u]:
        if v==fa:continue
        dfs1(v,u)
        s[u]+=s[v]
        mmin=max(mmin,s[v])
    mmin=max(mmin,n-s[u])
    if mmin < ans:
        ans,res=mmin,u
    elif mmin==ans and u < res :res=u

dfs1(1,0)
print(res,ans)

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 396K, 提交时间: 2022-09-20 13:40:59

#include<bits/stdc++.h>

using namespace std;

int n,f[1003],u,v,a1=1e9,a2=1e9;
vector<int> g[1003];
void dfs(int u,int p){
    f[u] = 1;int m = 0;
    for(auto k:g[u]) if(k!=p) dfs(k,u),f[u]+=f[k],m=max(m,f[k]);m=max(m,n-f[u]);
    if(m<a2)a2=m,a1=u;else if(m==a2&&a1>u)a1=u;
}
int main() {
    cin >> n;
    for(int i=1;i<n;i++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u);
    dfs(1,0), cout << a1 << ' ' << a2 << endl;
}