【图论】树剖（上）：重链剖分

一、前置知识清单

1. 深度优先搜索DFS 点我复习
2. 图的存储 复习链接敬请期待
3. 树状数组 点我复习

二、树剖简介

树剖（树链剖分），是一种把树划分成链的算法，该算法分为重链剖分和长链剖分。
本文仅讨论重链剖分，长链剖分目前本人还不会，所以不予展示。

三、模拟重链剖分

图6是一棵树，我们钦定1号结点为根。

图6

若要对这棵树进行重链剖分，首先要求出它的DFN序。注意这里的DFN序与DFS序还是有一定区别的。 DFN序就是优先遍历每个结点重儿子的DFS序。
以上面的图6为例，我们先求出以每个结点为根的子树重量 $si{z}_i$（即以每个结点为根的子树所包含的结点个数）。该树中 $si{z}_i$ 分别等于 $5$，$2$，$1$，$4$，$1$。
对于每个非叶子结点，找到其 $si{z}_i$ 最大的儿子（即重儿子），记为 $so{n}_i$。若有多个儿子的 $si{z}_i$ 相等，则 $so{n}_i$ 取任意一个儿子均可。该树中 $so{n}_i$ 分别等于 $4$，$3$，$0$，$2$，$0$。
我们将每个重儿子和它的父亲连接，形成一条条重链。该树中有两条重链：$1$，$4$，$2$，$3$ 为一条重链，$5$ 自成一条重链。

四、代码实现重链剖分

感谢@xixisuper_提供树剖代码。由于本人一顿操作，代码变得又长又唐，请见谅。

#include<bits/stdc++.h>
using namespace std;
vector<int>e[114514];
int fa[114514],dep[114514],siz[114514],son[114514];
//fa[i]存储每个非根节点的父亲，dep[i]存储每个结点的深度 
void dfs(int u,int father){
int lz;
fa[u]=father;
dep[u]=dep[father]+1;
siz[u]=1;
lz=e[u].size();
for(int i=0;i<lz;i++){
if(e[u][i]==father)continue;//避免回搜 
dfs(e[u][i],u);//本人的十手笔记本电脑写了auto会编译错误 
siz[u]+=siz[e[u][i]];
if(siz[son[u]]<siz[e[u][i]]) son[u]=e[u][i];
}
}//找重儿子 
int dfn[114514],nidfn[114514],top[114514],tot;
//dfn[i]存储DFN序（点到下标），nidfn[i]存储逆DFN序（下标到点），你只需要知道这两个东西很有用就行了 
//top[i]存储链顶 
void pf(int u,int father){
int lz; 
dfn[u]=++tot; 
nidfn[tot]=u;
if(son[u]){
top[son[u]]=top[u];
pf(son[u],u);//先遍历重儿子 
}
lz=e[u].size();
for(int i=0;i<lz;i++){
if(e[u][i]==father)continue;//避免回搜 
if(e[u][i]==son[u])continue;//重儿子已经遍历过了 
top[e[u][i]]=e[u][i];
pf(e[u][i],u);
}
}//剖分，求DFN序 
int lowbit(int x){
return x&(-x);
}
struct st{
//使用树状数组维护区间和 
int c[114514];
void add(int x,int y){
for(int i=x;i<=y;i+=lowbit(i))c[i]+=y;//单点修改 
return;
}
void add(int x,int y,int z){
for(int i=x;i<=y;i++)add(i,z);//这里的区间修改貌似有点怪怪的，有什么可以优化的地方请私信我，备注142719158
return; 
}
int query(int x){
int r=0;//前缀查询
for(int i=x;i;i-=lowbit(i))r+=c[i];
return r;
}
int query(int x,int y){
return query(y)-query(x-1);//区间查询 
}
}tr;
void update(int x,int y,int z){
//将x与y之间唯一路径上的点点权加上z
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
tr.add(dfn[top[x]],dfn[x],z);//当两个结点不在同一条链上时，深度更大的结点向上跳 
x=fa[top[x]];//向上跳到链顶的父亲 
}
else{
tr.add(dfn[top[y]],dfn[y],z);
y=fa[top[y]];//向上跳到链顶的父亲 
}
}
if(dep[x]>dep[y])tr.add(dfn[y],dfn[x],z);
else tr.add(dfn[x],dfn[y],z);
return; 
}
int qry(int x,int y){
//查询x与y之间唯一路径上的点点权之和 
int r=0; 
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]]){
r+=tr.query(dfn[top[x]],dfn[x]);//当两个结点不在同一条链上时，深度更大的结点向上跳 
x=fa[top[x]];//向上跳到链顶的父亲 
}
else{
r+=tr.query(dfn[top[y]],dfn[y]);
y=fa[top[y]];//向上跳到链顶的父亲 
}
}
if(dep[x]>dep[y])r+=tr.query(dfn[y],dfn[x]);
else r+=tr.query(dfn[x],dfn[y]);
return r;
}
int main(){
dfs(1,0);
top[1]=1;
pf(1,0);
return 0;
}

如果博客有错误，或者发现了代码中的问题，请联系我，备注142719158，我会尽快修正！鲁A济南车！

原文地址：https://blog.csdn.net/muyangquan0013/article/details/142719158

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！