[luoguP2486] [SDOI2011]染色（树链剖分）

传送门

就是个模板啦

记录每一个点的左端点颜色和右端点颜色和当前端点颜色段数。

合并时如果左孩子右端点和右孩子左端点不同就ans

在重链上跳的时候别忘记统计一下

——代码

#include <cstdio> #include <cstring> #include <iostream> #define N 001 #define ls now << 1 #define rs now << 1 | 1 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) #define pushup(now) Lcol[now] = Lcol[ls], Rcol[now] = Rcol[rs], col[now] = col[ls] + col[rs] (Rcol[ls] == Lcol[rs]) int n, m, cnt, tim; int head[N], to[N << 1], next[N << 1]; int a[N], f[N], deep[N], size[N], son[N], tid[N], top[N], rank[N], L[N], R[N], Lcol[N], Rcol[N], col[N], laz[N]; inline int read() inline void add(int x, int y) inline void dfs1(int u) } } inline void dfs2(int u, int t) } inline void build(int now, int l, int r) int mid = (l + r) >> 1; build(ls, l, mid); build(rs, mid + 1, r); pushup(now); } inline void pushdown(int now) } inline void update(int now, int l, int r, int z) pushdown(now); int mid = (L[now] + R[now]) >> 1; if(l <= mid) update(ls, l, r, z); if(mid < r) update(rs, l, r, z); pushup(now); } inline void q_update(int u, int v, int z) if(deep[u] > deep[v]) swap(u, v); update(1, tid[u], tid[v], z); } inline int q_color(int now, int x) inline int query(int now, int l, int r) inline int q_query(int u, int v) if(deep[u] > deep[v]) swap(u, v); ans += query(1, tid[u], tid[v]); return ans; } int main() dfs1(1); dfs2(1, 1); build(1, 1, n); for(i = 1; i <= m; i++) else printf("%d\n", q_query(x, y)); } return 0; }

　　

上一篇：[luoguP1197] [JSOI2008]星球大战（并查集）

下一篇：[BZOJ2594] [Wc2006]水管局长数据加强版（LCT + kruskal + 离线）

---

树链剖分