[luoguP2982][USACO10FEB]慢下来Slowing down（dfs序 + 线段树）

传送门

这个题显然可以用树链剖分做。

然而线段树也能做。

每个点都对它的子树有贡献，所以先求一边 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）

下一篇：[POJ3041] Asteroids（最小点覆盖-匈牙利算法）

---

线段树 dfs 树链剖分 dfs序