树的重心

luckydrawbox · 2022-09-03 23:56:37 · 个人记录

变量

函数

代码

struct Tree_Center{
    int sum;
    int sze[N],weight[N];
    int center[3],center_cnt;
    void init(){
        center_cnt=0;
        memset(sze,0,sizeof(sze));
        memset(weight,0,sizeof(weight));
        memset(center,0,sizeof(center));
    }
    void dfs(int x,int fa){
        sze[x]=1;
        weight[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(y==fa)
                continue;
            dfs(y,x);
            sze[x]+=sze[y];
            weight[x]=max(weight[x],sze[y]);
        }
        weight[x]=max(weight[x],sum-sze[x]);
        if(weight[x]<=sum/2)
            center[++center_cnt]=x;
    }
    void ask(int root,int n){
        sum=n;
        init();
        dfs(root,0);
    }
}tree;