相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4817
解题报告
我们发现涂色可以看作LCT的access操作
然后权值就是到根的虚边数
于是用LCT来维护颜色
用线段树配合DFS序来支持查询
时间复杂度:$O(n \log^2 n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = N << 1; const int LOG = 20; int n, m, head[N], nxt[M], to[M]; int in[N], ot[N], dep[N], num[N], ff[N][LOG]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar()); for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar()); return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline int LCA(int u, int v) { if (dep[u] < dep[v]) { swap(u, v); } for (int j = LOG - 1; ~j; j--) { if (dep[ff[u][j]] >= dep[v]) { u = ff[u][j]; } } if (u == v) { return u; } for (int j = LOG - 1; ~j; j--) { if (ff[u][j] != ff[v][j]) { u = ff[u][j]; v = ff[v][j]; } } return ff[u][0]; } class SegmentTree{ int root, ch[M][2], tag[M], mx[M]; public: inline void init() { build(root, 1, n); } inline void modify(int l, int r, int d) { modify(root, 1, n, l, r, d); } inline int query(int l, int r = -1) { return query(root, 1, n, l, r >= 0? r: l); } private: inline void PushDown(int w) { if (tag[w]) { int ls = ch[w][0], rs = ch[w][1]; mx[ls] += tag[w]; mx[rs] += tag[w]; tag[ls] += tag[w]; tag[rs] += tag[w]; tag[w] = 0; } } inline int query(int w, int l, int r, int L, int R) { if (L <= l && r <= R) { return mx[w]; } else { PushDown(w); int mid = l + r + 1 >> 1, ret = 0; if (L < mid) { ret = max(ret, query(ch[w][0], l, mid - 1, L, R)); } if (mid <= R) { ret = max(ret, query(ch[w][1], mid, r, L, R)); } return ret; } } inline void modify(int w, int l, int r, int L, int R, int d) { if (L <= l && r <= R) { tag[w] += d; mx[w] += d; } else { PushDown(w); int mid = l + r + 1 >> 1; if (L < mid) { modify(ch[w][0], l, mid - 1, L, R, d); } if (mid <= R) { modify(ch[w][1], mid, r, L, R, d); } mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]); } } inline void build(int &w, int l, int r) { static int cnt = 0; w = ++cnt; if (l == r) { mx[w] = dep[num[l]]; } else { int mid = l + r + 1 >> 1; build(ch[w][0], l, mid - 1); build(ch[w][1], mid, r); mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]); } } }SGT; class LinkCutTree{ int ch[N][2], fa[N]; public: inline void SetFather(int w, int f) { fa[w] = f; } inline void access(int x) { for (int last = 0; x; last = x, x = fa[x]) { splay(x); if (fa[x]) { int p = GetMin(x); SGT.modify(in[p], ot[p], -1); } if (ch[x][1]) { int p = GetMin(ch[x][1]); SGT.modify(in[p], ot[p], 1); } ch[x][1] = last; } } private: inline bool IsRoot(int x) { return !fa[x] || (ch[fa[x]][0] != x && ch[fa[x]][1] != x); } inline int GetMin(int x) { return ch[x][0]? GetMin(ch[x][0]): x; } inline void splay(int x) { for (int f, ff; !IsRoot(x); ) { f = fa[x], ff = fa[f]; if (IsRoot(f)) { rotate(x); } else { if ((ch[ff][0] == f) ^ (ch[f][0] == x)) { rotate(x); rotate(x); } else { rotate(f); rotate(x); } } } } inline void rotate(int x) { int f = fa[x], t = ch[f][1] == x; fa[x] = fa[f]; if (!IsRoot(f)) { ch[fa[f]][ch[fa[f]][1] == f] = x; } ch[f][t] = ch[x][t ^ 1]; fa[ch[x][t ^ 1]] = f; ch[x][t ^ 1] = f; fa[f] = x; } }LCT; inline void DFS(int w, int f) { static int ID = 0; LCT.SetFather(w, f); ff[w][0] = f; dep[w] = dep[f] + 1; num[in[w] = ++ID] = w; for (int i = head[w]; i; i = nxt[i]) { if (to[i] != f) { DFS(to[i], w); } } ot[w] = ID; } int main() { n = read(); m = read(); for (int i = 1; i < n; i++) { AddEdge(read(), read()); } DFS(1, 0); for (int j = 1; j < LOG; j++) { for (int i = 1; i <= n; i++) { ff[i][j] = ff[ff[i][j - 1]][j - 1]; } } SGT.init(); for (int i = 1; i <= m; i++) { int opt = read(); if (opt == 1) { LCT.access(read()); } else if (opt == 2) { int u = read(), v = read(), lca = LCA(u, v); printf("%d\n", SGT.query(in[u]) + SGT.query(in[v]) - 2 * SGT.query(in[lca]) + 1); } else { int x = read(); printf("%d\n", SGT.query(in[x], ot[x])); } } return 0; }