传送门
这个题显然可以用树链剖分做。
然而线段树也能做。
每个点都对它的子树有贡献，所以先求一边 dfs序，然后直接在 dfs序 中搞 线段树 就行。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #define root 1, 1, n 4 #define ls now << 1, l, mid 5 #define rs now << 1 | 1, mid + 1, r 6 7 using namespace std; 8 9 const int MAXN = 100001; 10 int n, cnt, tim; 11 int head[MAXN], to[MAXN << 1], next[MAXN << 1], add[MAXN << 2], tid[MAXN], size[MAXN]; 12 13 inline void add_edge(int x, int y) 14 19 20 inline void dfs(int u) 21 30 } 31 32 inline void push_down(int now) 33 39 40 inline int query(int x, int now, int l, int r) 41 48 49 inline void update(int x, int y, int now, int l, int r) 50 56 if(l > y || r < x) return; 57 push_down(now); 58 int mid = (l + r) >> 1; 59 update(x, y, ls); 60 update(x, y, rs); 61 } 62 int main() 64 74 dfs(1); 75 for(i = 1; i <= n; i++) 76 81 return 0; 82 }View Code
上一篇：[luoguP1077] 摆花（DP）
下一篇：[POJ3233] Matrix Power Series（矩阵快速幂）
线段树 dfs序 dfs 树链剖分
