长链剖分
长链剖分可以视作是dsu on tree算法的一个特例，在学习之前，需要掌握树链剖分以及dsu on tree。
dsu on tree用于解决：
子树类的静态查询类问题。
基础复杂度为)
。
长链剖用于解决：
子树类与深度相关可合并的静态查询类问题。
基础复杂度为)
。
长链剖应用的场景必须是与子树深度相关的，从这点上来讲他只是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;
} 这一次是长链剖分，数组的意义有的发生了改变。 同样的，
在数值上与
相同。
我们想一下dsu on tree的dsu函数的过程。
dsu(x)
{
1、处理轻儿子
2、处理重儿子
3、把轻儿子的信息往重儿子上边并
4、计算答案
5、需要清空时清空统计用的数据结构
} 他这个算法过程其实还算比较繁琐，为什么需要这么麻烦呢，原因在于：统计用的数据结构，是所有节点共用的。这就导致每次统计的时候如果a不是b的子问题，就必须对数据结构进行初始化。 刚刚我们需要维护子树信息，这个东西它拆不开，而现在我们仅维护的是长链信息，换句话说就是仅保留以x为根节点时的向下的长链信息。
大人，时代变了，我可以把这个统计用的数据结构仅让每条长链中的节点共用（换句话说就是,
表示的覆盖作用域变了，使得不同链之间的作用域无交）。
现在的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，那为什么它是的呢。
长链剖的合并是集合的合并，换句话说就是sum[y]表示的是以x为根深度为y的这个集合的点权和。
它可以类比成一开始有n个集合，我做若干次集合的合并之后剩下了m个集合，问合并的复杂度，那就是)
。
长链剖每次合并深度相同的不同短链时，都至少使得两个节点所在的集合发生了合并，那么至多合并n次。
又由于它不像dsu on tree一样重置了数据结构进行重新扫描，所以节点只能越并越少,合并所需的代价就是*%E5%8D%95%E7%82%B9%E5%90%88%E5%B9%B6%E5%A4%8D%E6%9D%82%E5%BA%A6%20%5Cright))
。
所以长链剖的基础时间复杂度就是的。
当然，你会查询某一子树深度节点的和，那你也会查询某一子树深度在一定区间范围的节点和咯。套个线段树进去就好了，线段树单点修改的复杂度为)
所以总的复杂度就是)
咯。
当然，你会查询某一子树深度节点的和，那你也会查询某一子树深度在一定区间范围的节点和咯。套个线段树进去就好了，线段树单点修改的复杂度为
子树类与深度无关可合并的静态查询类问题
请直接树形DP，本来可合并的问题就该树形DP解决的，只不过与深度相关时开不下这么大的数组才需要长链剖或者dsu on tree，这点做题的灵活性还是要有的。
投递中国南方电网等公司10个岗位 >