传送门
看着很吓人，其实就是个树链剖分模板。
可支持操作：
1.将节点 x 到 根 的路径上的值都变成 1
2.将以节点 x 为根的子树的值都变成 0
1A爽~
——代码
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define root 1, 1, n 6 #define ls now << 1, l, mid 7 #define rs now << 1 | 1, mid + 1, r 8 9 const int MAXN = 1000001; 10 int n, m, cnt, tim, ans; 11 int head[MAXN], to[MAXN], next[MAXN]; 12 int f[MAXN], son[MAXN], size[MAXN], deep[MAXN], tid[MAXN], top[MAXN], sum[MAXN << 2], turn[MAXN << 2]; 13 14 inline int read() 15 22 23 inline void add(int x, int y) 24 29 30 inline void dfs1(int u) 31 42 } 43 44 inline void dfs2(int u, int tp) 45 55 } 56 57 inline void swap(int &x, int &y) 58 61 62 inline void pushup(int now) 66 67 inline void pushdown(int now, int len) 68 76 77 inline void update(int x, int ql, int qr, int now, int l, int r) 78 86 if(r < ql || l > qr) return; 87 pushdown(now, r l + 1); 88 int mid = (l + r) >> 1; 89 update(x, ql, qr, ls); 90 update(x, ql, qr, rs); 91 pushup(now); 92 } 93 94 inline void qupdate(int x, int u, int v) 95 102 if(deep[u] > deep[v]) swap(u, v); 103 update(x, tid[u], tid[v], root); 104 } 105 106 int main() 107 120 dfs1(0); 121 dfs2(0, 0); 122 m = read(); 123 for(i = 1; i <= m; i++) 124 132 return 0; 133 }View Code
上一篇：[luoguP3572] [POI2014]PTA-Little Bird（DP + 单调队列）
下一篇：[luoguP1440] 求m区间内的最小值（单调队列 || 线段树）
树链剖分 线段树
