bzoj4817 & loj2001 [Sdoi2017]树点涂色 LCT + 线段树

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4817

https://loj.ac/problem/2001

题解

可以发现这个题就是 bzoj3779 重组病毒 的弱化版。

可以这样考虑。对于每一次染色操作，都是把 \(x\) 点到根的路径上的点全部染成一种颜色。

我们考虑用一个东西来记录下来同色的点，可以发现这个操作和 LCT 的 access 操作很像。如果用 LCT 来维护的话，那么就是一个 splay 记录一堆同色的点。

然后 access 的断掉重儿子的时候相当于是在重儿子里面集体加 \(1\)，连上新的重儿子就是集体 \(-1\)。这个可以用线段树维护。

然后第二个操作可以树上差分，那么就是 \(f_x + f_y - 2f_{lca} + 1\)。

因为 LCT 的性质，时间复杂度 \(O(m\log^2n)\)。

#include

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back

template inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair pii;

template inline void read(I &x) {
	int f = 0, c;
	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
	x = c & 15;
	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
	f ? x = -x : 0;
}

const int N = 100000 + 7;

int n, m, dfc;
int dep[N], f[N], siz[N], son[N], dfn[N], pre[N], top[N];

struct Edge { int to, ne; } g[N << 1]; int head[N], tot;
inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }
inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

namespace SGT {
	#define lc o << 1
	#define rc o << 1 | 1
	struct Node { int add, max; } t[N << 2];
	inline void build(int o, int L, int R) {
		t[o].add = 0;
		if (L == R) return t[o].max = dep[pre[L]], (void)0;
		int M = (L + R) >> 1;
		build(lc, L, M), build(rc, M + 1, R);
		t[o].max = std::max(t[lc].max, t[rc].max);
	}
	inline void qadd(int o, int L, int R, int l, int r, int k) {
		if (l <= L && R <= r) return t[o].add += k, t[o].max += k, (void)0;
		int M = (L + R) >> 1;
		if (l <= M) qadd(lc, L, M, l, r, k);
		if (r > M) qadd(rc, M + 1, R, l, r, k);
		t[o].max = std::max(t[lc].max, t[rc].max) + t[o].add;
	}
	inline int qmax(int o, int L, int R, int l, int r) {
		if (l <= L && R <= r) return t[o].max;
		int M = (L + R) >> 1;
		if (r <= M) return qmax(lc, L, M, l, r) + t[o].add;
		if (l > M) return qmax(rc, M + 1, R, l, r) + t[o].add;
		return std::max(qmax(lc, L, M, l, r), qmax(rc, M + 1, R, l, r)) + t[o].add;
	}
	#undef lc
	#undef rc
}

namespace LCT {
	#define lc c[0]
	#define rc c[1]
	struct Node { int c[2], fa; } t[N];
	inline bool isroot(int o) { return t[t[o].fa].lc != o && t[t[o].fa].rc != o; }
	inline bool idtfy(int o) { return t[t[o].fa].rc == o; }
	inline void connect(int fa, int o, int d) { t[fa].c[d] = o, t[o].fa = fa; }
	inline void rotate(int o) {
		int fa = t[o].fa, pa = t[fa].fa, d1 = idtfy(o), d2 = idtfy(fa), b = t[o].c[d1 ^ 1];
		if (!isroot(fa)) t[pa].c[d2] = o; t[o].fa = pa;
		connect(o, fa, d1 ^ 1), connect(fa, b, d1);
	}
	inline void splay(int o) {
		while (!isroot(o)) {
			int fa = t[o].fa;
			if (isroot(fa)) rotate(o);
			else if (idtfy(o) == idtfy(fa)) rotate(fa), rotate(o);
			else rotate(o), rotate(o);
		}
	}
	inline void access(int o) {
		for (int x = 0; o; o = t[x = o].fa) {
			splay(o);
			if (t[o].rc) {
				int p = t[o].rc;
				while (t[p].lc) p = t[p].lc;
				SGT::qadd(1, 1, n, dfn[p], dfn[p] + siz[p] - 1, 1);
				splay(p), splay(o);
			}
			t[o].rc = x;
			if (t[o].rc) {
				int p = t[o].rc;
				while (t[p].lc) p = t[p].lc;
				SGT::qadd(1, 1, n, dfn[p], dfn[p] + siz[p] - 1, -1);
				splay(p), splay(o);
			}
		}
	}
	#undef lc
	#undef rc
}

inline void dfs1(int x, int fa = 0) {
	dep[x] = dep[fa] + 1, f[x] = fa, siz[x] = 1, LCT::t[x].fa = fa;
	for fec(i, x, y) if (y != fa) dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);
}
inline void dfs2(int x, int pa) {
	top[x] = pa, dfn[x] = ++dfc, pre[dfc] = x;
	if (!son[x]) return; dfs2(son[x], pa);
	for fec(i, x, y) if (y != f[x] && y != son[x]) dfs2(y, y);
}
inline int lca(int x, int y) {
	while (top[x] != top[y]) dep[top[x]] > dep[top[y]] ? x = f[top[x]] : y = f[top[y]];
	return dep[x] < dep[y] ? x : y;
}

inline void work() {
	dfs1(1), dfs2(1, 1);
	SGT::build(1, 1, n);
	while (m--) {
		int opt, x, y, p;
		read(opt);
		if (opt == 1) read(x), LCT::access(x);
		else if (opt == 2) read(x), read(y), p = lca(x, y), printf("%d\n", SGT::qmax(1, 1, n, dfn[x], dfn[x]) + SGT::qmax(1, 1, n, dfn[y], dfn[y]) - (SGT::qmax(1, 1, n, dfn[p], dfn[p]) << 1) + 1);
		else read(x), printf("%d\n", SGT::qmax(1, 1, n, dfn[x], dfn[x] + siz[x] - 1));
	}
}

inline void init() {
	read(n), read(m);
	int x, y;
	for (int i = 1; i < n; ++i) read(x), read(y), adde(x, y);
}

int main() {
#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
#endif
	init();
	work();
	fclose(stdin), fclose(stdout);
	return 0;
}