传送门
树链剖分固然可以搞。
但还有另一种做法，可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。
而给以某一节点 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
上一篇：[POJ2594] Treasure Exploration（最小路径覆盖-传递闭包 + 匈牙利算法）
下一篇：[POJ3041] Asteroids（最小点覆盖-匈牙利算法）
线段树 树链剖分 dfs序 dfs
