NC15033 小G有一个大树

树的直径模板。

const int N=1e5+10;
vector<int> g[N];
int n;
int ans=N;
int pos;

int dfs(int u,int fa)
{
    int tot=1; // 以u为根的子树大小
    int maxchild=0;
    for(int i=0;i<g[u].size();i++)
    {
        int j=g[u][i];
        if(j == fa) continue;
        int cnt=dfs(j,u);
        maxchild=max(maxchild,cnt);
        tot+=cnt;
    }

    maxchild=max(maxchild,n-tot);
    if(maxchild < ans)
    {
        ans=maxchild;
        pos=u;
    }
    else if(maxchild == ans && u < pos)
        pos=u;
    
    return tot;
}

int main()
{
    cin>>n;

    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(1,-1);
    
    cout<<pos<<‘ ‘<<ans<<endl;
    //system("pause");
    return 0;
}

NC15033 小G有一个大树

原文：https://www.cnblogs.com/fxh0707/p/14634277.html