【模板】树链剖分
[ZJOI2008]树的统计
洛谷传送门
第一遍树链剖分，打的很难受。
其中拉闸了，检查真是费劲。
树链剖分是什么？
树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。
树链剖分可以支持链上求和，链上求最值，链上修改等线段树的操作。
但若断开一条边或者连接两个点，保证两个点连接后依然是棵树。这样树链剖分就虚了，因为线段树不支持这种操作，就需要把线段树换成splay，于是LCT = 树剖 + splay。
将树中的边分为：轻边和重边 ?定义size(X)为以X为根的子树的节点个数。 ?令V为U的儿子节点中size值最大的节点，那么边(U,V)被称为重边，树中重边之外的边被称为轻边。性质：?轻边(U,V)，size(V)<=size(U)/2。 ?从根到某一点的路径上，不超过O(logN)条轻边，不超过O(logN)条重路径。
说明：
重孩子：儿子节点所有孩子中size最大的
轻孩子：儿子节点中除了重儿子的节点
重边：连接重儿子的边
轻边：连接轻儿子的边
重链：重边连成的链
轻链：轻边连成的链
a[i] 表示节点 i 权值
f[i] 表示节点 i 的父亲在原树中的位置
son[i] 表示节点 i 的重儿子在原树中的位置
top[i] 表示节点 i 所在链的顶端节点在原树中的位置，就是深度最小的
size[i] 表示以 i 为根的子树节点个数
tid[i] 表示树中节点 i 剖分后的新编号
rank[i] 表示剖分后的节点 i 在原树中的位置
deep[i] 表示节点 i 深度，根节点深度为 1
实现方法：
第一遍dfs可以预处理出size，deep，f，son数组
第二遍dfs可以预处理出top，tid，rank数组，通过优先搜索重边，然后搜索轻边
树链剖分目的是把树上的边剖分成一个链，就是一个线段，标号是连续的。
为什么要先搜索重边呢？
可以看出，这样搜可以使得重链上的点的dfs序是连续的，可以用线段树来维护。
如何查询呢？
判断两点是否属于同一条重链，如果属于，就直接修改，因为他们是连续的，如果不属于，就从深度大点开始不停地找他父亲跳轻链，其中深度是不停地在变的，也就是说，两个点可能会轮着跳，直到属于同一个重链。现在看来，轻边实际上是连接重链的东西。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define rt 1, 1, n 5 #define ls o << 1, l, m 6 #define rs o << 1 | 1, m + 1, r 7 8 using namespace std; 9 10 const int maxn = 300001; 11 const int INF = 99999999; 12 int n, m, q, cnt, tim; 13 int a[maxn], head[maxn], to[maxn << 2], next[maxn << 2], deep[maxn], size[maxn]; 14 int son[maxn], top[maxn], f[maxn], tid[maxn], rank[maxn], sumv[maxn], maxv[maxn]; 15 //a节点权值, deep节点深度, size以x为根的子树节点个数, son重儿子, top当前节点所在链的顶端节点 16 //f当前节点父亲, tid保存树中每个节点剖分后的新编号, rank保存剖分后的节点在线段树中的位置 17 18 void add(int x, int y) 19 24 25 void dfs1(int u, int father)//记录所有重边 26 39 } 40 41 void dfs2(int u, int tp) 42 54 } 55 56 void pushup(int o) 57 61 62 void updata(int o, int l, int r, int d, int x) 70 if(d <= m) updata(ls, d, x); 71 else updata(rs, d, x); 72 pushup(o); 73 } 74 75 void build(int o, int l, int r) 76 83 build(ls); 84 build(rs); 85 pushup(o); 86 } 87 88 int querymax(int o, int l, int r, int ql, int qr) 89 97 98 int qmax(int u, int v) 99 107 if(deep[u] < deep[v]) swap(u, v);//在同一条重链上了 108 ans = max(ans, querymax(rt, tid[v], tid[u])); 109 return ans; 110 } 111 112 int querysum(int o, int l, int r, int ql, int qr) 113 121 122 int qsum(int u, int v) 123 131 if(deep[u] < deep[v]) swap(u, v);//在同一条重链上了 132 ans += querysum(rt, tid[v], tid[u]); 133 return ans; 134 } 135 136 int main() 137 149 for(i = 1; i <= n; i++) scanf("%d", &a[i]); 150 dfs1(1, 1);//根节点和他的父亲 151 dfs2(1, 1);//根节点和链头结点 152 build(rt); 153 scanf("%d", &q); 154 for(i = 1; i <= q; i++) 155 161 return 0; 162 }View Code
洛谷模板题
检查了n遍代码，检查了n遍函数，都没有检查出错误来。
最后偶然发现只是因为调用错了函数。。。
这道题要使一个子树的值都加x，且统计子树所有节点的值的和。
可以发现，一个子树上的点在线段树中的编号是连续的，所以可以对区间 ( tim[x], tim[x] + size[x] 1 ) 进行操作。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define LL long long 5 #define rt 1, 1, n 6 #define ls o << 1, l, m 7 #define rs o << 1 | 1, m + 1, r 8 9 using namespace std; 10 11 const int maxn = 100001; 12 int n, m, s, cnt, tim; 13 int head[maxn], next[maxn << 2], to[maxn << 2], deep[maxn], f[maxn], size[maxn], son[maxn], top[maxn], rank[maxn], tid[maxn]; 14 LL p, a[maxn], sumv[maxn << 2], addv[maxn << 2]; 15 16 void add(int x, int y) 17 22 23 void dfs1(int u, int father) 24 37 } 38 39 void dfs2(int u, int tp) 40 52 } 53 54 void pushup(int o) 55 58 59 void pushdown(int o, int len) 60 67 68 void build(int o, int l, int r) 69 75 int m = (l + r) >> 1; 76 build(ls); 77 build(rs); 78 pushup(o); 79 } 80 81 void updata(int o, int l, int r, int ql, int qr, LL d) 82 89 if(l > qr || r < ql) return; 90 if(addv[o]) pushdown(o, r l + 1); 91 int m = (l + r) >> 1; 92 updata(ls, ql, qr, d); 93 updata(rs, ql, qr, d); 94 pushup(o); 95 } 96 97 void qdata(int u, int v, LL d) 98 105 if(deep[u] > deep[v]) swap(u, v); 106 updata(rt, tid[u], tid[v], d); 107 } 108 109 LL querysum(int o, int l, int r, int ql, int qr) 110 117 118 LL qsum(int u, int v) 119 127 if(deep[u] > deep[v]) swap(u, v); 128 ans = (ans + querysum(rt, tid[u], tid[v])) % p; 129 return ans; 130 } 131 132 int main() 133 146 dfs1(s, s);//根节点和他的父亲 147 dfs2(s, s);//根节点和链头结点 148 build(rt); 149 for(i = 1; i <= m; i++) 150 157 else if(c == 2) 158 162 else if(c == 3) 1 167 else 168 172 } 173 return 0; 174 }View Code
上一篇：运动员最佳匹配问题（km算法）
下一篇：公路修建（Prim）
线段树 模板 树链剖分