本文主要是介绍长链剖分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

基槽：

优化转移时间复杂度只和深度有关的树形DP

思想：

定义重儿子为深度最大的儿子，每次巧妙地利用数组分配空间的方式(利用dfn序)继承来自重儿子的信息，然后暴力合并亲儿子，均摊时空复杂度\(O(n)\)。

Pf：定义长链为最长的全是由重儿子组成的链，则长链的顶点一定是一个轻儿子,对于每个点，只存在于一条长链上，每条长链只会合并一次，需要深度大小的时间，合并后根节点的深度不会发生变化。

所以可以大胆地把时间均摊到每个节点，均摊\(O(1)\).

Luogu P3565 [POI2014]HOT-Hotels

显然3个点不可能在一条链上，只可能是（先找两个点）

第二种情况好弄，第一种情况本能想到换根，但由于每次和深度有关，所以无法换根DP

\(f[u][i]\)表示\(u\)的子树中深度为\(i\)的节点个数

正难则反，之所以无法换根DP是因为无法维护fa的深度数组，所以考虑维护\(g[u][i]\)表示u的子树中还需要\(i\)的距离的点对数量即可

void dgs(int fa,int u) {
    f[u][1]=1;
    for(int e=he[u];e;e=nxt[e]) {
        int v=to[e];
        if(v!=fa) {
            dgs(u,v);
            for(int i=0;i<=dep[v];i++) {
                if(i) ans+=(ll)f[u][i-1]*g[v][i];
                ans+=(ll)g[u][i+1]*f[v][i];
            }
            for(int i=1;i<=dep[v]+1;i++) {
                g[u][i]+=g[v][i+1]+(ll)f[u][i]*f[v][i-1];
                f[u][i]+=f[v][i-1];
            }
        }
    }
    ans+=g[u][0];
}

长链剖分（此为无dfn序版本）

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e5+5;
int n,cnt,id,to[N],nxt[N],he[N],son[N],dep[N],sf[N],sg[N];
ll t[N],ans;


inline void add(int u,int v) {
    to[++cnt]=v,nxt[cnt]=he[u],he[u]=cnt;
}

void dfs(int fa,int u) {
    for(int e=he[u];e;e=nxt[e]) {
        int v=to[e];
        if(v!=fa) {
            dfs(u,v); 
            if(dep[v]>dep[son[u]]) son[u]=v;
        }
    }
    dep[u]=dep[son[u]]+1;
}

void dgs(int fa,int u) {
    if(son[u]) {
        sf[son[u]]=sf[u]+1,sg[son[u]]=sg[u]-1;
        dgs(u,son[u]);
        ans+=t[sg[u]];
    }
    t[sf[u]]=1;
    for(int e=he[u];e;e=nxt[e]) {
        int v=to[e];
        if(v!=fa&&v!=son[u]) {
            sf[v]=id,id+=(dep[v]<<1); sg[v]=id; id+=(dep[v]<<1);
            dgs(u,v);
            for(int i=0;i<=dep[v];i++) {
                if(i) ans+=(ll)t[sf[u]+i-1]*t[sg[v]+i];
                ans+=(ll)t[sg[u]+i+1]*t[sf[v]+i];
            }
            for(int i=0;i<dep[v];i++) {
                t[sg[u]+i]+=(ll)t[sg[v]+i+1];
            }
            for(int i=1;i<=dep[v]+1;i++) {
                t[sg[u]+i]+=(ll)t[sf[u]+i]*t[sf[v]+i-1];
                t[sf[u]+i]+=t[sf[v]+i-1];
            }
        }
    }
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        int u,v; scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(0,1);
    sf[1]=id; id+=(dep[1]<<1); sg[1]=id; id+=(dep[1]<<1);
    dgs(0,1);
    printf("%lld\n",ans);
    return 0;
} 

这篇关于长链剖分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！