【算法笔记】树链剖分

整理的算法模板合集： ACM模板

一些概念

重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；
轻儿子：父亲节点中除了重儿子以外的儿子；
重边：父亲结点和重儿子连成的边；
轻边：父亲节点和轻儿子连成的边；
重链：由多条重边连接而成的路径；
轻链：由多条轻边连接而成的路径；

一些性质

重链剖分可以将树上的任意一条路径划分成不超过 $l o g n$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。
树上每个节点都属于且仅属于一条重链。
重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。
所有的重链将整棵树完全剖分。
在剖分时优先遍历重儿子，最后重链的 DFS 序就会是连续的。
在剖分时重边优先遍历，最后树的 DFN 序上，重链内的 DFN 序是连续的。按 DFN 排序后的序列即为剖分后的链。
一颗子树内的 DFN 序是连续的。
可以发现，当我们向下经过一条轻边时，所在子树的大小至少会除以二。因此，对于树上的任意一条路径，把它拆分成从 LCA分别向两边往下走，分别最多走 $l o g n$ 次，因此，树上的每条路径都可以被拆分成不超过 $l o g n$ 条重链。

实现

主要思想：暴力就是艺术

主要算法步骤：

dfs找重儿子，标记深度，父节点。
分配dfs序链接重链，标记每条重链的顶端（当并查集使用）
开始暴力跳，两个点先跳到同一个重链上，跳的同时记录权值，跳完以后直接求两点之间的权值即可（此时已在同一个重链上了）。
乱搞

我们每一条重链在线段树都是连续的一段区间。

P3384 【模板】轻重链剖分

在这里插入图片描述

半个多小时写了二百多行的树链剖分找了一个多小时的bug结果是因为我的线段树没有初始化l，r 。＞﹏＜

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>using namespace std;
typedef long long ll;
const int N = 200007, M = 5000007, INF = 0x3f3f3f3f;int n, m;
int root, mod;
int head[N], ver[M], edge[M], nex[M], tot;
int a[N], a_after[N];
struct Tree{int l, r;int lz;int sum;
}tr[N * 4];
int son[N];//重儿子
int id[N], fa[N], cnt, deep[N], sizes[N];
int top[N]; //重链顶点
int res = 0;void add(int x, int y)
{ver[tot] = y;nex[tot] = head[x];head[x] = tot ++ ;
}inline void pushup(int p)
{tr[p].sum = (tr[p << 1].sum + tr[p << 1 | 1].sum) % mod;
}inline void pushdown(int p)
{auto &root = tr[p], &left = tr[p << 1], &right = tr[p << 1 | 1];if(!root.lz)return ;left.lz += root.lz;right.lz += root.lz;left.sum = (left.sum + root.lz * (left.r - left.l + 1)) % mod;right.sum = (right.sum + root.lz * (right.r - right.l + 1)) % mod;root.lz = 0;
}void build(int p, int l, int r)
{tr[p] = {l, r, 0, 0};if(l == r){tr[p].sum = a_after[l];//10 % 10 = 0;if(tr[p].sum > mod)tr[p].sum %= mod;return ;}int mid = l + r >> 1;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);pushup(p);
}int query(int p, int l, int r)
{if(tr[p].l >= l && tr[p].r <= r){return tr[p].sum % mod;}pushdown(p);int mid = tr[p].l + tr[p].r >> 1;int res = 0;if(l <= mid)res = (res + query(p << 1, l, r)) % mod;if(r > mid)res = (res + query(p << 1 | 1, l, r)) % mod;return res;
}void modify(int p, int l, int r, int k)
{if(tr[p].l >= l && tr[p].r <= r){tr[p].lz += k;tr[p].sum += k * (tr[p].r - tr[p].l + 1);return ;}int mid = tr[p].l + tr[p].r >> 1;pushdown(p);if(l <= mid)modify(p << 1, l, r, k);if(r > mid)modify(p << 1 | 1, l, r, k);pushup(p);return ;
}//-----------------------线段树
//找重儿子，记录深度
void dfs_son(int x, int father, int deeps)
{deep[x] = deeps;fa[x] = father;sizes[x] = 1;int max_son = -1;for(int i = head[x]; ~i; i = nex[i]){int y = ver[i];if(y == father)continue;dfs_son(y, x, deeps + 1);sizes[x] += sizes[y];if(sizes[y] > max_son)son[x] = y,max_son = sizes[y];}
}//链接重链
void dfs_build(int x, int topfa)
{id[x] = ++ cnt;a_after[cnt] = a[x];//!把每个点的初始值赋值到新编号上top[x] = topfa;if(!son[x])return ;//!如果没有重儿子就返回dfs_build(son[x], topfa);for(int i = head[x]; ~i; i = nex[i]){int y = ver[i];if(y == fa[x] || y == son[x])continue;dfs_build(y, y);//对于每一个轻儿子都有一条从它自己开始的链}
}int query_range(int x, int y)
{int res = 0;//类似并查集while(top[x] != top[y]){//当不在一条（重）链上时if(deep[top[x]] < deep[top[y]])swap(x, y);//一步一步查询，查询当前点到链顶的权值和，直到x和y在同一条重链上为止res = (res + query(1, id[top[x]], id[x])) % mod;//深度由小到大，编号由小到大x = fa[top[x]];//往上跳}//当前已经在一条链上了，所以不用再比较top[x],top[y]了if(deep[x] > deep[y])//让x更浅，这样x的编号小(编号是重儿子优先的dfs序)（因为此时x和y在同一条重链上）（一条重链的编号是连续的）swap(x, y);res = (res + query(1, id[x], id[y])) % mod;//已经到同一条链上了，再加上这条链上的权值和return res;
}void update_range(int x, int y, int z)//同样的操作，其实树链剖分就是暴力
{z %= mod;while(top[x] != top[y]){if(deep[top[x]] < deep[top[y]])swap(x, y);modify(1, id[top[x]], id[x], z);x = fa[top[x]];}if(deep[x] > deep[y])swap(x, y);modify(1, id[x], id[y], z);
}
//处理子树
//因为以任意一个点作为根，它的子树内的点的 dfs 序都是连续的，所以我们只
//需要记录以每个节点为根的子树中新编号最大的那个节点的新编号即可，自己的
//新编号到最大的编号就是以自己为根的子树的新编号的范围。
int query_son(int x)
{return query(1, id[x], id[x] + sizes[x] - 1);
}void update_son(int x, int k)
{modify(1, id[x], id[x] + sizes[x] - 1, k);
}//----------------树链剖分
int main()
{memset(head, -1, sizeof head);scanf("%d%d%d%d", &n, &m, &root, &mod);for(int i =1; i <= n; ++ i)scanf("%d", &a[i]);for(int i = 1; i < n; ++ i){int x, y;scanf("%d%d", &x, &y);add(x, y);add(y, x);}dfs_son(root, 0, 1);dfs_build(root, root);build(1, 1, n);while(m -- ){int x, y, z, k;scanf("%d", &k);if(k == 1){scanf("%d%d%d", &x, &y, &z);update_range(x, y, z);}else if(k == 2){scanf("%d%d", &x, &y);printf("%d\n", query_range(x, y));}else if(k == 3){scanf("%d%d", &x, &y);update_son(x, y);}else {scanf("%d", &x);printf("%d\n", query_son(x));}}return 0;
}