相关链接
题目传送门：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;
}
