[模板] 长链剖分

刺骨的言语ヽ痛彻心扉 2022-01-08 00:41 233阅读 0赞

## 长链剖分 ##

*  [长链剖分学习总结 | Bill Yang's Blog][_ Bill Yang_s Blog]

### 简介 ###

对每个节点 \\(p\\), 定义 \\(\\operatorname\{len\} (p)\\) 表示 \\(p\\) 到它子树中叶子节点的最大长度.

类似重链剖分, 把每个节点 \\(p\\) 的儿子中 \\(\\operatorname\{len\}\\) 最大的设为它的重儿子. 边 \\((p,son(p))\\) 称为重边.

把重边组成的极长子链称为重链(或者长链).

长链剖分可以保证一个性质:

\\\[\\begin\{equation\} \\text\{长链总长度\} \\le n \\end\{equation\}\\\]

虽然很显然, 但这个性质保证了一些利用长链剖分的算法的复杂度.

### 应用 ###

#### 求一个点的k级祖先 ####

预处理 \\(O(n \\log n)\\), 单次询问 \\(O(1)\\).

其实并没有什么卵用, 可以被倍增替代

#### 优化一些关于长度的dp ####

先咕了...

## 例题: bzoj4543: \[POI2014\]Hotel加强版 ##

可以得到一个关于链长度的dp方程, 因此利用长链剖分优化即可.

开空间时:

*  对于\\(f\\) 数组, 重链顶 \\(p\\) 和它的重链上的儿子只会用到 \\(mem\[f\[p\] ... f\[p\]+len\[p\]-1\]\\) 的空间;
 *  对于\\(g\\) 数组, 重链顶 \\(p\\) 和它的重链上的儿子会用到 \\(mem\[g\[p\]-len\[p\]+1 ... g\[p\]+len\[p\]-1\]\\) 的空间.

因此开空间时需要开两倍... 详见代码.

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<set>
    #include<map>
    using namespace std;
    #define rep(i,l,r) for(register int i=(l);i<=(r);++i)
    #define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
    #define il inline
    typedef double db;
    typedef long long ll;
    
    //---------------------------------------
    const int nsz=100050;
    
    int n;
    ll ans=0;
    struct te{int t,pr;}edge[nsz*2];
    int hd[nsz],pe=1;
    void adde(int f,int t){edge[++pe]=(te){t,hd[f]};hd[f]=pe;}
    void adddb(int f,int t){adde(f,t);adde(t,f);}
    #define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t)
    
    int len[nsz]{-1},son[nsz];
    ll mem[nsz*5],*f[nsz],*g[nsz],*pm=mem;
    void initp(int p,int l){ //开空间
        f[p]=pm,pm+=(l<<1)+2,g[p]=pm,pm+=l+2;
    }
    
    void dfs1(int p,int f){
        son[p]=0,len[p]=0;
        forg(p,i,v){
            if(v==f)continue;
            dfs1(v,p);
            if(len[v]>len[son[p]])son[p]=v,len[p]=len[v]+1;
        }
    }
    
    void dfs2(int p,int fa){
        if(son[p]){
            f[son[p]]=f[p]+1,g[son[p]]=g[p]-1;
            dfs2(son[p],p);
        }
        f[p][0]=1;
        ans+=g[p][0];
        forg(p,i,v){
            if(v==fa||v==son[p])continue;
            initp(v,len[v]);
            dfs2(v,p);
            rep(j,0,len[v]){
                if(j)ans+=f[p][j-1]*g[v][j];
                ans+=g[p][j+1]*f[v][j];
            }
            rep(j,0,len[v]){
                g[p][j+1]+=f[p][j+1]*f[v][j];
                if(j)g[p][j-1]+=g[v][j];
                f[p][j+1]+=f[v][j];
            }
        }
    }
    
    int main(){
        ios::sync_with_stdio(0),cin.tie(0);
        cin>>n;
        int a,b;
        rep(i,1,n-1)cin>>a>>b,adddb(a,b);
        dfs1(1,0);
        initp(1,len[1]);
        dfs2(1,0);
        cout<<ans<<'\n';
        return 0;
    }

转载于:https://www.cnblogs.com/ubospica/p/10485904.html

[_ Bill Yang_s Blog]: https://blog.bill.moe/long-chain-subdivision-notes/