有的类似于线段树的题目 是对树上的某点或点与点之间的路径进行修改, 然后查询某点或点与点之间路径的一些性质
像这样的题目虽然类似线段树 但是却无法简单就用线段树来做
因为线段树只能存储节点的一些性质 对于路径就无能为力了
因此我们需要将树 和路径 分开, 使得每一条链和线段树的区间对应 就是树链剖分
当然树链剖分也不仅限于与线段树结合
树链剖分很很多种方法, 普遍用到的是轻重边剖分
我们首先将树中的边分为两部分, 轻边和重边, 记 size(U)为以 U 为根的子树的节点的个数, 令 V 为 U 的儿子中 size 最大的一个 (如有多个最大, 只取一个), 则我们说边(U,V) 为重边, 其余的边为轻边(如下图所示红色为重边, 蓝色为轻边).
我们将一棵树的所有边按上述方法分成轻边和重边后, 我们可以得到以下几个性质:
1: 若 (U,V) 为轻边, 则 size(V)<=size(U)/2.
这是显然的.
2: 从根到某一点的路径上轻边的个数不会超过 O(logN),(N 为节点总数).
这也是很简单, 因为假设从跟 root 到 v 的路径有 k 条轻边, 它们是 root->...->v1->...->v2->......->vk->...->v, 我们设 size(v)=num, 显然 num>=1, 则由性质 1, 我们有 size(Vk)>=2,size(Vk-1)>=4......size(v1)>=2^k, 显然有 2^k<=N, 所以 k<=log2(N).
如果我们把一条链中的连续重边连起来, 成为重链, 则一条链就变成了轻边与重链交替分段的链, 且段数是 log(N)级别的, 则我们可以将重链放在线段树中维护, 轻边可放可不放, 为了方便一般还是放, 但是速度就会打一点折扣了.
定义这样一些值:
- const int MAXN = (100000 <<2) + 10;
- ?
- //Heavy-light Decomposition STARTS FORM HERE
- int siz[MAXN];//number of son
- int top[MAXN];//top of the heavy link
- int son[MAXN];//heavy son of the node
- int dep[MAXN];//depth of the node
- int faz[MAXN];//father of the node
- int tid[MAXN];//ID -> DFSID
- int rnk[MAXN];//DFSID -> ID
算法大致需要进行两次的 DFS, 第一次 DFS 可以得到当前节点的父亲结点(faz 数组), 当前结点的深度值(dep 数组), 当前结点的子结点数量(size 数组), 当前结点的重结点(son 数组)
- void dfs1(int u, int father, int depth) {
- /*
- * u: 当前结点
- * father: 父亲结点
- * depth: 深度
- */
- // 更新 dep,faz,siz 数组
- dep[u] = depth;
- faz[u] = father;
- siz[u] = 1;
- ?
- // 遍历所有和当前结点连接的结点
- for (int i = head[u]; i; i = edg[i].next) {
- int v = edg[i].to;
- // 如果连接的结点是当前结点的父亲结点, 则不处理
- if (v != faz[u]) {
- dfs1(v, u, depth + 1);
- // 收敛的时候将当前结点的 siz 加上子结点的 siz
- siz[u] += siz[v];
- // 如果没有设置过重结点 son 或者子结点 v 的 siz 大于之前记录的重结点 son, 则进行更新
- if (son[u] == -1 || siz[v]> siz[son[u]]) {
- son[u] = v;
- }
- }
- }
- }
第二次 DFS 的时候则可以将各个重结点连接成重链, 轻节点连接成轻链, 并且将重链 (其实就是一段区间) 用数据结构 (一般是树状数组或线段树) 来进行维护, 并且为每个节点进行编号, 其实就是 DFS 在执行时的顺序(tid 数组), 以及当前节点所在链的起点(top 数组), 还有当前节点在树中的位置(rank 数组).
- void dfs2(int u, int t) {
- /**
- * u: 当前结点
- * t: 起始的重结点
- */
- top[u] = t; // 设置当前结点的起点为 t
- tid[u] = cnt; // 设置当前结点的 dfs 执行序号
- rnk[cnt] = u; // 设置 dfs 序号对应成当前结点
- cnt++;
- ?
- // 如果当前结点没有处在重链上, 则不处理
- if (son[u] == -1) {
- return;
- }
- // 将这条重链上的所有的结点都设置成起始的重结点
- dfs2(son[u], t);
- // 遍历所有和当前结点连接的结点
- for (int i = head[u]; i; i = edg[i].next) {
- int v = edg[i].to;
- // 如果连接结点不是当前结点的重子结点并且也不是 u 的父亲结点, 则将其的 top 设置成自己, 进一步递归
- if (v != son[u] && v != faz[u]){
- dfs2(v, v);
- }
- }
- }
而修改和查询操作原理是类似的, 以查询操作为例, 其实就是个 LCA, 不过这里使用了 top 来进行加速, 因为 top 可以直接跳转到该重链的起始结点, 轻链没有起始结点之说, 他们的 top 就是自己. 需要注意的是, 每次循环只能跳一次, 并且让结点深的那个来跳到 top 的位置, 避免两个一起跳从而插肩而过.
- INT64 query_path(int x, int y) {
- /**
- * x: 结点 x
- * y: 结点 y
- * 查询结点 x 到结点 y 的路径和
- */
- INT64 ans = 0;
- int fx = top[x], fy = top[y];
- // 直到 x 和 y 两个结点所在链的起始结点相等才表明找到了 LCA
- while (fx != fy) {
- if (dep[fx]>= dep[fy]) {
- // 已经计算了从 x 到其链中起始结点的路径和
- ans += query(1, tid[fx], tid[x]);
- // 将 x 设置成起始结点的父亲结点, 走轻边, 继续循环
- x = faz[fx];
- } else {
- ans += query(1, tid[fy], tid[y]);
- y = faz[fy];
- }
- fx = top[x], fy = top[y];
- }
- ?
- // 即便找到了 LCA, 但是前面也只是分别计算了从一开始到最终停止的位置和路径和
- // 如果两个结点不一样, 表明仍然需要计算两个结点到 LCA 的路径和
- if (x != y) {
- if (tid[x] <tid[y]) {
- ans += query(1, tid[x], tid[y]);
- } else {
- ans += query(1, tid[y], tid[x]);
- }
- } else ans += query(1, tid[x], tid[y]);
- return ans;
- }
- ?
- void update_path(int x, int y, int z) {
- /**
- * x: 结点 x
- * y: 结点 y
- * z: 需要加上的值
- * 更新结点 x 到结点 y 的值
- */
- int fx = top[x], fy = top[y];
- while(fx != fy) {
- if (dep[fx]> dep[fy]) {
- update(1, tid[fx],tid[x], z);
- x = faz[fx];
- } else {
- update(1, tid[fy], tid[y], z);
- y = faz[fy];
- }
- fx = top[x], fy = top[y];
- }
- if (x != y)
- if (tid[x] < tid[y]) update(1, tid[x], tid[y], z);
- else update(1, tid[y], tid[x], z);
- else update(1, tid[x], tid[y], z);
- }
树链剖分
来源: http://www.bubuko.com/infodetail-2770947.html