点分治

luckydrawbox · 2022-08-28 21:03:40 · 个人记录

变量

函数

代码

int n;
int a[N],tt,d[N],s[N],mx[N];
int root,S;
bool v[N];
void get_root(int x,int fa){
    s[x]=1;
    mx[x]=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(v[y]||y==fa)
            continue;
        get_root(y,x);
        s[x]+=s[y];
        mx[x]=max(mx[x],s[y]);
    }
    mx[x]=max(mx[x],S-s[x]);
    if(mx[x]<mx[root])
        root=x;
}
void get_dis(int x,int fa){
    a[++tt]=d[x];
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i],z=edge[i];
        if(v[y]||y==fa)
            continue;
        d[y]=d[x]+z;
        get_dis(y,x);
    }
}
void calc(int x){
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i],z=nxt[i];
        if(v[y])
            continue;
        d[y]=z;
        get_dis(y,x);
        //solve the problem
    }
}
void DFZ(int x){
    v[x]=1;
    calc(x);
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(v[y])
            continue;
        S=s[y];
        mx[root=0]=1e9;
        get_root(y,0);
        DFZ(root);
    }
}
void ask(){
    S=n;
    mx[root=0]=1e9;
    get_root(1,0);
    DFZ(root);
}