树与dfs.树的重心.acwing 846

树与dfs.树的重心.acwing 846

code:

#include<bits/stdc++.h>//xfl
using namespace std;
const int N = 2e5+10;
int h[N],ne[N],to[N],siz[N];
int n,num,minn=N;
void add(int a,int b){ne[++num]=h[a];to[num]=b;h[a]=num;}
void dfs(int x,int fa)
{
    siz[x]=1;
    int maxx=0;
    for(int i=h[x];i;i=ne[i])
        if(to[i]!=fa)
        {
            dfs(to[i],x);
            siz[x]+=siz[to[i]];
            maxx=max(maxx,siz[to[i]]);
        }
    maxx=max(maxx,n-siz[x]);
    minn=min(minn,maxx);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    cout<<minn;
    return 0;
}

 

上一篇:【第846期】你不懂JS:异步流程控制


下一篇:P1075 [NOIP2012 普及组] 质因数分解