长链剖分_牛客博客

长链剖分可以视作是dsu on tree算法的一个特例，在学习之前，需要掌握树链剖分以及dsu on tree。

dsu on tree:https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98

dsu on tree用于解决：

子树类的静态查询类问题。

基础复杂度为 $O(nlog_2n)$ 。

长链剖用于解决：

子树类与深度相关可合并的静态查询类问题。

基础复杂度为 $O\left( n \right)$ 。

长链剖应用的场景必须是与子树深度相关的，从这点上来讲他只是dsu on tree的特例。

当然，它的复杂度是比dsu on tree要优秀的，不然不就完爆了么（长链剖可解决的问题都能用dsu on tree来解决,当然你强行用吧，多个log问题其实也不大，dsu on tree常数很小一般不会特地卡）

有些博客中的长链剖分O(1)的重链转移部分会使用指针避开下标运算，但是我这里不使用指针，因为指针版在套用其他数据结构时不够灵活。

算法方面大部分与dsu on tree相同，直接从代码的不同点开始说起吧。

例题：给一颗以1为根大小为n的有根树，每个点有点权，查询若干次，每次查询以x的子树，深度为y的这一层中，所有点权的和（节点x的深度为0）。

第一行输入一个n表示树尺寸，接下来输入一行n个整数表示每个节点的权值。然后输入n-1行表示一棵树。

接下来输入m表示查询的次数。

接下来m行每行两个整数x,y表示查询以x为根的子树，深度为y这层所有点权的权值和（深度从0开始计算）。

链剖部分

void dfs1(int x,int father)
{
    fa[x]=father;
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=father)
        {
            dfs1(e[i].to,x);
            if(!son[x]||len[son[x]]<len[e[i].to])son[x]=e[i].to;
        }
    }
    len[x]=len[son[x]]+1;
    return;
}
void dfs2(int x)
{
    L[x]=++dfn;
    R[x]=L[x]+len[x]-1;
    if(son[x])dfs2(son[x]);
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=fa[x]&&e[i].to!=son[x])
        {
            dfs2(e[i].to);
        }
    }
    return;
}

这一次是长链剖分，数组的意义有的发生了改变。

$fa\left[ x \right]$ 表示父节点， $len\left[ x \right]$ 表示以x为长链的头时，长链的最长长度。 $son\left[ x \right]$ 还是重儿子，不过这次是长链的重儿子， $L\left[ x \right]$ , $R\left[ x \right]$ 和之前dsu on tree的含义不同，这次表示x节点的下属长链中dfn的最小值与最大值。

同样的， $L\left[ x \right]$ 在数值上与 $id\left[ x \right]$ 相同。

我们想一下dsu on tree的dsu函数的过程。

dsu(x)
{
    1、处理轻儿子
    2、处理重儿子
    3、把轻儿子的信息往重儿子上边并
    4、计算答案
    5、需要清空时清空统计用的数据结构
}

他这个算法过程其实还算比较繁琐，为什么需要这么麻烦呢，原因在于：统计用的数据结构，是所有节点共用的。这就导致每次统计的时候如果a不是b的子问题，就必须对数据结构进行初始化。

刚刚我们需要维护子树信息，这个东西它拆不开，而现在我们仅维护的是长链信息，换句话说就是仅保留以x为根节点时的向下的长链信息。

大人，时代变了，我可以把这个统计用的数据结构仅让每条长链中的节点共用（换句话说就是 $L\left[ x \right]$ , $R\left[ x \right]$ 表示的覆盖作用域变了，使得不同链之间的作用域无交）。

现在的dfs序列为{1,2,4,6,7,3,5}

L[1]=1,R[1]=4

L[7]=5,R[7]=5

L[3]=6,R[3]=7
每一条重链所使用的数组内存是完全无交的，也就是数据结构仅被同一重链的节点所共用。

dsu(x)
{
    1、处理轻儿子
    2、处理重儿子
    3、把轻儿子的信息往重儿子上边并
    4、计算答案
    5、需要清空时清空统计用的数据结构
}

那这个过程首先，他并不需要清空数据结构，5这条就可以删了。（dsu on tree因为不同子树是共用一个数据结构，所以每次处理完不同的子树都需要init一下，而现在不共用，那就不需要清空了）

dsu(x)
{
    1、处理轻儿子
    2、处理重儿子
    3、把轻儿子的信息往重儿子上边并
    4、计算答案
}

那好，既然都不共用数据结构了，那其实我先处理轻儿子还是先处理重儿子，它没区别，我顺序就可以自由换了，那么我调整一下顺序，把1、3这两条放在一起一块做。（dsu on tree因为先处理的子树需要init重置数据结构，最后处理的子树才能被保留，所以最后处理重儿子，而现在不共用，所以无所谓处理顺序）

dsu(x)
{
    1、处理重儿子
    2、处理轻儿子同时把轻儿子的信息往重儿子上边并
    3、计算答案
}

因为它只用处理深度相关的问题，所以比起dsu on tree，少了很多限制条件，那他也太好写了。

void dsu(int x)
{
    if(son[x])
    {
        dsu(son[x]);
    }
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=fa[x]&&e[i].to!=son[x])
        {
            dsu(e[i].to);
            for(int j=L[e[i].to],k=1;j<=R[e[i].to];++j,++k)
            {
                sum[L[x]+k]+=sum[j];
            }
        }
    }
    sum[L[x]]+=val[x];
    for(auto &i:lis[x])
    {
        ans[i.first]=sum[L[x]+i.second];
    }
    return;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int tot,g[MAXN],len[MAXN],L[MAXN],R[MAXN],fa[MAXN],son[MAXN],dfn,n,m,x,y,u,v;
long long val[MAXN],ans[MAXN],sum[MAXN];

vector<pair<int,int> >lis[MAXN];

struct edges
{
    int to,next;
}e[2*MAXN];

void add_edge(int from,int to)
{
    e[++tot].to=to;
    e[tot].next=g[from];
    g[from]=tot;
    return;
}

void dfs1(int x,int father)
{
    fa[x]=father;
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=father)
        {
            dfs1(e[i].to,x);
            if(!son[x]||len[son[x]]<len[e[i].to])son[x]=e[i].to;
        }
    }
    len[x]=len[son[x]]+1;
    return;
}
void dfs2(int x)
{
    L[x]=++dfn;
    R[x]=L[x]+len[x]-1;
    if(son[x])dfs2(son[x]);
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=fa[x]&&e[i].to!=son[x])
        {
            dfs2(e[i].to);
        }
    }
    return;
}
void dsu(int x)
{
    if(son[x])
    {
        dsu(son[x]);
    }
    for(int i=g[x];i;i=e[i].next)
    {
        if(e[i].to!=fa[x]&&e[i].to!=son[x])
        {
            dsu(e[i].to);
            for(int j=L[e[i].to],k=1;j<=R[e[i].to];++j,++k)
            {
                sum[L[x]+k]+=sum[j];
            }
        }
    }
    sum[L[x]]+=val[x];
    for(auto &i:lis[x])
    {
        ans[i.first]=sum[L[x]+i.second];
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&val[i]);
    }
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(1,0);
    dfs2(1);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&x,&y);
        lis[x].push_back(make_pair(i,y));
    }
    dsu(1);
    for(int i=1;i<=m;++i)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

样例输入：
7
1 2 3 4 5 6 7
1 2
1 3
2 4
4 7
4 6
3 5
6
1 1
1 2
4 0
5 0
4 1
1 3
样例输出：
5
9
4
5
13
13

复杂度分析

这个算法和dsu on tree的相比少了个log，那为什么它是 $O\left( n \right)$ 的呢。

长链剖的合并是集合的合并，换句话说就是sum[y]表示的是以x为根深度为y的这个集合的点权和。

它可以类比成一开始有n个集合，我做若干次集合的合并之后剩下了m个集合，问合并的复杂度，那就是 $O \left( n-m \right)$ 。

长链剖每次合并深度相同的不同短链时，都至少使得两个节点所在的集合发生了合并，那么至多合并n次。

又由于它不像dsu on tree一样重置了数据结构进行重新扫描，所以节点只能越并越少,合并所需的代价就是 $O \left( (n-deep)*单点合并复杂度 \right)$ 。

所以长链剖的基础时间复杂度就是 $O\left( n \right)$ 的。
当然，你会查询某一子树深度节点的和，那你也会查询某一子树深度在一定区间范围的节点和咯。套个线段树进去就好了，线段树单点修改的复杂度为 $O\left( log_2n \right)$ 所以总的复杂度就是 $O\left( nlog_2n \right)$ 咯。

子树类与深度无关可合并的静态查询类问题

请直接树形DP，本来可合并的问题就该树形DP解决的，只不过与深度相关时开不下这么大的数组才需要长链剖或者dsu on tree，这点做题的灵活性还是要有的。