重链剖分
前置芝士：线段树，dfs 序，LCA
概念
- 一个非叶子节点，他的儿子中子树大小最大的就是重儿子，否则就是轻儿子
- 对于一条边，如果连接的子节点是重儿子，那么这条边就是重边，否则就是轻边
- 重链：如果一条链中的边都是重边，那么这条链就是重链
重要结论
一个节点到根节点的路径上最多不超过 \(\log n\) 条重链
证明
（以下用 \(now\) 表示当前节点，\(fa\) 表示 \(now\) 的父节点，\(son_{fa}\) 表示父节点的重儿子，\(size_u\) 表示 \(u\) 子树的大小）
由于经过 \(\log n\) 条重链后，那么就会经过 \(\log n\) 条轻边
那么只需要证明经过一条轻边后 \(size\) 至少会变为原来的 \(2\) 倍就行了
再分类讨论一下：
如果 \(size_{son_{fa}} \le \dfrac{size_{fa}}2\) ，那么显然可以得到 \(size_{now} \le \dfrac{size_{fa}}2\) ，那么经过这条轻边后 \(size\) 至少会变成原来的 \(2\) 倍
否则，$size_{son_{fa}} > \dfrac{size_{fa}}2 $，那么由于 \(size_{now}\le size_{fa}-size_{son_{fa}}\)，那么可以得到 \(size_{now} < \dfrac {size_{fa}} 2\)，那么经过这条轻边后 \(size\) 至少也会变成原来的 \(2\) 倍
dfs1
dfs 时我们需要处理出以下数组：
-
\(fa_u\) ：表示 \(u\) 节点的父节点
-
\(depth_u\) ：表示 \(u\) 节点的深度
-
\(size_u\) ：表示以 \(u\) 节点为根的子树的大小
-
\(son_u\) ：表示 \(u\) 节点的重儿子
Code
（代码里的注释已经讲的很清楚了）
void dfs1(int u,int f)
{
fa[u]=f,size[u]=1;
depth[u]=depth[f]+1;
for (int v:g[u])
if (v!=f) {
dfs1(v,u); size[u]+=size[v]; //统计当前节点的子树大小
if (size[v]>size[son[u]]) son[u]=v; //记录重儿子
}
}
dfs2
这次我们需要处理出以下数组：
- \(top_u\) ：\(u\) 所在的重链的链顶
- \(id_u\) ： \(u\) 节点在 dfs 序中的编号
不过这次 dfs 时我们要先遍历重儿子，再遍历轻儿子，原因后面再说
Code
void dfs2(int u,int topf) //topf：u所在的重链的链顶
{
top[u]=topf,id[u]=(++cnt);
if (son[u]) dfs2(son[u],topf); //注意这里要先判断当前节点是否为叶节点
for (int v:g[u])
if (!top[v])
dfs2(v,v); //轻儿子所在的重链的链顶就是它本身
}
树上操作
由于 dfs2 时是先遍历的重儿子，再遍历的轻儿子，那么树上每条重链的 \(id\) 都是连续的
由于是 dfs ，那么子树内的 \(id\) 也是连续的
这样就方便用数据结构维护了
处理子树
处理 \(x\) 子树：
直接在数据结构上处理 \([id_x,id_{x+size_x-1}]\) 区间就行了
代码就不放了
处理树上路径
处理树上 \(x\) 到 \(y\) 的路径：
我们可以先把路径分成两部分：\(x\) 到 \(LCA(x,y)\) 和 \(y\) 到 \(LCA(x,y)\)
我们再回想下求 \(LCA\) 的最朴素的写法：就是只要 \(x\) 和 \(y\) 不相等就选择最深的节点往上跳
那么这里我们也用类似的做法：只要 \(x\) 和 \(y\) 不在同一条重链里，就选择重链链顶深度高的那个跳到链顶的父节点，同时在处理它到链顶的这条链，\(x\) 和 \(y\) 在同一条重链后还要再处理 \(x\) 到 \(y\) 的这条链
Code
void solve(int x,int y)
{
while (top[x]!=top[y]) {
if (depth[top[x]]<depth[top[y]]) swap(x,y);
//处理线段树上 id[top[x]]~id[x] 区间
x=fa[top[x]];
}
if (depth[x]>depth[y]) swap(x,y);
//处理线段树上 id[y]~id[y] 区间
}
处理边权问题
先把边权存到边连接的深度更大的点上，再进行处理
但是处理树上路径时，当 \(top_x=top_y\) 后，应该改成处理 \([id_x+1,id_y]\) 区间
因为此时 \(x\) 就为原来的 \(x\) 和 \(y\) 的 LCA 了，由于 LCA 上的点权存的是 \(fa_{LCA}\) 到 LCA 的边权，就不在 \(x\) 到 \(y\) 的路径上了