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

一、前置知识清单

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);//这里的区间修改貌似有点怪怪的，有什么可以优化的地方请私信我，备注142719158return; }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之间唯一路径上的点点权加上zwhile(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济南车！