[luoguP3178] [HAOI2015]树上操作（dfs序 + 线段树 || 树链剖分）

传送门

树链剖分固然可以搞。

但还有另一种做法，可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。

而给以某一节点 x 为根的子树增加一个权值也会影响当前子树，节点 y 所增加的值为 dis[y] * z (dis[x] 1) * z，每个节点都会增加 (dis[x] 1) * z ，

询问时只用加上 dis[y] * y和当前节点 y 的权值。

给整棵子树增加一个权值可以用 dfs 序 + 线段树搞， dis 数组可以预处理出来。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #define LL long long 4 #define root 1, 1, n 5 #define ls now << 1, l, mid 6 #define rs now << 1 | 1, mid + 1, r 7 8 using namespace std; 9 10 const int MAXN = 100001; 11 int n, m, cnt, tot; 12 int head[MAXN], next[MAXN << 1], to[MAXN << 1], tid[MAXN], size[MAXN]; 13 LL a[MAXN << 2], b[MAXN << 2], val[MAXN], dis[MAXN]; 14 15 inline void add(int x, int y) 16 21 22 inline void dfs(int u) 23 36 } 37 } 38 39 inline void push_down(int now) 40 47 48 inline void update(LL x, LL y, int ql, int qr, int now, int l, int r) 49 56 push_down(now); 57 int mid = (l + r) >> 1; 58 if(ql <= mid) update(x, y, ql, qr, ls); 59 if(mid < qr) update(x, y, ql, qr, rs); 60 } 61 62 inline LL query(int u, int x, int now, int l, int r) 70 71 int main() 72 84 dis[1] = 1; 85 dfs(1); 86 for(i = 1; i <= n; i++) update(0, val[i], tid[i], tid[i] + size[i] 1, root); 87 for(i = 1; i <= m; i++) 88 95 else if(z == 2) 96 100 else printf("%lld\n", query(x, tid[x], root)); 101 } 102 return 0; 103 }
View Code

上一篇：[luoguP3258] [JLOI2014]松鼠的新家（lca + 树上差分）

下一篇：负环

---

线段树 dfs 树链剖分 dfs序