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

思路

题目都没看懂就莫名其妙A了，“如果结点数相同输出编号小的”，是指平衡点的编号吗？下面题解是按照这样理解的。
我先讲一下做题思路吧，数据规模很小，1e3，所以可以把每一个节点当作根去找树的最大深度，最大深度最小的第一个节点可以作为平衡点。
找到平衡点之后再来一个push_up对他每一个子节点计算树的节点数，就能求出答案了。

代码

#include<bits/stdc++.h>
#define int ll
#define inf 0x3f3f3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn=1e5+5;
int n,a[maxn],u,v,tmp,ans=0,id;
int sz[maxn],dep[maxn],tmp_dep=0,mx_dep=1e6+7;
vector<int>G[maxn];

int push_up(int node,int pre){
    sz[node]=1;
    for(int i=0;i<G[node].size();i++){
        if(G[node][i]==pre) continue;
        sz[node]+=push_up(G[node][i],node);
    }
    return sz[node];
} 

void dfs(int node,int pre){
//    cout<<node<<" "<<pre<<endl;
    for(int i=0;i<G[node].size();i++){
        int to=G[node][i];
        if(to==pre) continue;
        dep[to]=dep[node]+1;
        dfs(to,node);
    }
    tmp_dep=max(dep[node],tmp_dep);
}

signed main(){
    scanf("%lld",&n);
    for(int i=1;i<n;i++){
        scanf("%lld%lld",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        memset(dep,0,sizeof(dep));
        tmp_dep=0;
        dfs(i,0);
        if(tmp_dep<mx_dep){
            mx_dep=tmp_dep;
            id=i;
        }
    }
//    cout<<mx_dep<<" "<<id<<endl;
    for(int i=0;i<=G[id].size();i++){
        tmp=push_up(G[id][i],id);
        if(tmp>ans) ans=tmp;
    }
    cout<<id<<" "<<ans;
    return 0;
}