[学习笔记]动态点分治

首先，动态点分治跟普通点分治几乎一模一样。所以点分治不会的可以右转模板区了。

我们发现处理树上路径不好处理，所以我们考虑点分治。但点分治带修改呢？

那动态点分治啊！

动态点分治就是建出原树的点分树，然后在点分树上暴力跳。因为点分树的高度是 \(log\ n\) 的，所以一般我们会再套一个 \(log\ n\) 的数据结构。

建出点分树：

void getrt(int x,int f){
    siz[x]=1;maxp[x]=0;
    for(int i=head[x],y;i;i=nxt[i]){
        y=to[i];
        if(y==f||vis[y]) continue;
        getrt(y,x);siz[x]+=siz[y];
        maxp[x]=max(maxp[x],siz[y]);
    }
    maxp[x]=max(maxp[x],sum-siz[x]);
    if(maxp[x]<maxp[rt]) rt=x;
}

void solve(int x,int f,int pre){
    fa[x]=f;vis[x]=1;
    for(int i=head[x],y;i;i=nxt[i]){
        y=to[i];
        if(vis[y]) continue;
        rt=0;sum=(siz[x]>siz[y])?siz[y]:pre-siz[x];
        getrt(y,x);solve(rt,x,siz[x]);
    }
}

我们发现其实就多了一句 \(fa[x]=f\)

题目：

【BZOJ1095】【ZJOI2007】捉迷藏

【Luogu3345】【ZJOI2015】幻想乡战略游戏

【BZOJ3730】震波

【BZOJ4372】烁烁的游戏

还没做完。我们以捉迷藏为例吧。

我们发现查询最远的两个点的距离其实就是取深度最大和次大的两个黑点。所以我们建出点分树，然后暴力上跳修改。

因为对于点分树的一条链都要修改，所以我们需要一个可以查询最大值和次大值，带删除的数据结构。

那肯定是双堆啊！

struct Heap{
    priority_queue<int> a,b;
    void push(int x){a.push(x);}
    void pop(int x){b.push(x);}
    int size(){return a.size()-b.size();}
    int top(){
        while(!b.empty()&&a.top()==b.top()) a.pop(),b.pop();
        return a.top();
    }
    int calc(){
        if(size()<2) return 0;
        int fir=top();pop(fir);
        int sec=top();push(fir);
        return fir+sec;
    }
};

我们发现时空复杂度都是 \(O(n\log^2 n)\)

因为做不到 \(O(n\log n)\)，所以查询树上两点路径我选择了倍增。

不开 \(O_2\) 还过不去。。。常数贼大

\(Code\ Below:\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int inf=0x3f3f3f3f;
int n,m,a[maxn],dep[maxn],f[maxn][18],cnt;
int fa[maxn],maxp[maxn],siz[maxn],vis[maxn],rt,sum;
int head[maxn],to[maxn<<1],nxt[maxn<<1],tot;

struct Heap{
    priority_queue<int> a,b;
    void push(int x){a.push(x);}
    void pop(int x){b.push(x);}
    int size(){return a.size()-b.size();}
    int top(){
        while(!b.empty()&&a.top()==b.top()) a.pop(),b.pop();
        return a.top();
    }
    int calc(){
        if(size()<2) return 0;
        int fir=top();pop(fir);
        int sec=top();push(fir);
        return fir+sec;
    }
}A[maxn],B[maxn],C;

inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
}

inline void addedge(int x,int y){
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

void dfs(int x,int fa){
    f[x][0]=fa;dep[x]=dep[fa]+1;
    for(int i=1;i<=17;i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x],y;i;i=nxt[i]){
        y=to[i];
        if(y==fa) continue;
        dfs(y,x);
    }
}

int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=17;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=17;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

int getdis(int x,int y){
    return dep[x]+dep[y]-2*dep[LCA(x,y)];
}

void getrt(int x,int f){
    siz[x]=1;maxp[x]=0;
    for(int i=head[x],y;i;i=nxt[i]){
        y=to[i];
        if(y==f||vis[y]) continue;
        getrt(y,x);siz[x]+=siz[y];
        maxp[x]=max(maxp[x],siz[y]);
    }
    maxp[x]=max(maxp[x],sum-siz[x]);
    if(maxp[x]<maxp[rt]) rt=x;
}

void solve(int x,int f,int pre){
    fa[x]=f;vis[x]=1;
    for(int i=head[x],y;i;i=nxt[i]){
        y=to[i];
        if(vis[y]) continue;
        rt=0;sum=(siz[x]>siz[y])?siz[y]:pre-siz[x];
        getrt(y,x);solve(rt,x,siz[x]);
    }
}

void turn_off(int u){
    B[u].push(0);
    if(B[u].size()==2) C.push(B[u].calc());
    int x,y,dis,lastdis,lastmax,lastsiz,nowmax,nowsiz;
    for(x=u;fa[x];x=fa[x]){
        y=fa[x];dis=getdis(u,y);
        lastdis=A[x].top();A[x].push(dis);
        if(dis<=lastdis) continue;
        lastmax=B[y].calc();lastsiz=B[y].size();
        if(lastdis) B[y].pop(lastdis);
        B[y].push(dis);
        nowmax=B[y].calc();nowsiz=B[y].size();
        if(nowmax>lastmax){
            if(lastsiz>=2) C.pop(lastmax);
            if(nowsiz>=2) C.push(nowmax);
        }
    }
}

void turn_on(int u){
    if(B[u].size()==2) C.pop(B[u].calc());
    B[u].pop(0);
    int x,y,dis,lastdis,lastmax,lastsiz,nowmax,nowsiz;
    for(x=u;fa[x];x=fa[x]){
        y=fa[x];dis=getdis(u,y);
        lastdis=A[x].top();A[x].pop(dis);
        if(dis<lastdis) continue;
        lastmax=B[y].calc();lastsiz=B[y].size();
        B[y].pop(lastdis);
        if(A[x].top()) B[y].push(A[x].top());
        nowmax=B[y].calc();nowsiz=B[y].size();
        if(nowmax<lastmax){
            if(lastsiz>=2) C.pop(lastmax);
            if(nowsiz>=2) C.push(nowmax);
        }
    }
}

int main()
{
    n=read();
    int x,y;char op;
    for(int i=1;i<n;i++){
        x=read(),y=read();
        addedge(x,y);addedge(y,x);
    }
    dfs(1,0);
    maxp[0]=inf;sum=n;
    getrt(1,0);solve(rt,0,n);
    for(int i=1;i<=n;i++) A[i].push(0);
    for(int i=1;i<=n;i++) cnt++,turn_off(i);
    m=read();
    while(m--){
        op=getchar();
        while(!isalpha(op)) op=getchar();
        if(op=='C'){
            x=read();
            if(a[x]==0) cnt--,turn_on(x);
            else cnt++,turn_off(x);
            a[x]^=1;
        }
        else {
            if(cnt==0) printf("-1\n");
            else if(cnt==1) printf("0\n");
            else printf("%d\n",C.top());
        }
    }
    return 0;
}

[学习笔记]动态点分治

原文：https://www.cnblogs.com/owencodeisking/p/10317939.html