【LCT、树状数组】CF1137F Matches Are Not a Child's Play

哈人*3400，是不是贺过了个 1F (?

单点编号 \(\to max + 1\)，动态维护 prufer 序列删除了哪些点。

看似不可做，但是不难发现我们一个点被更改其他点的相对次序不会改变，反而 \(x \to max\) 这条链的删除次序到了最后面。

然后我们以权值最大点为根，不难发现每次只是对根到该点的链更改了顺序，且顺序是从根到该点。

这个不就是 access 咩！！考虑树状数组维护每个颜色即可，考虑 makeroot 后，然后链上深度比该点大的点先删，所以加上右儿子即可。

时间复杂度 \(O(n \log^2 n)\)，没想到竟然跑的过去！有点快。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
/*为了芋泥啵啵我抽胖了双脸*/
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int _ = 5e5 + 5;

int n, m, tn;
vector <int> e[_];

struct Fenwick { 
	int c[_];
	void clr () {
		rep(i, 1, n) c[i] = 1;
		rep(i, 1, n + m) if (i + lowbit(i) <= n + m) c[i + lowbit(i)] += c[i]; 
	}
	void add (int x, int k) {
		while (x <= n + m) {
			c[x] += k, x += lowbit(x);
		}
		return ;
	}
	int query (int x) {
		int ret = 0;
		while (x) ret += c[x], x -= lowbit(x);
		return ret;
	}
} tr;

namespace LinkCutTree {
	int fa[_], ch[_][2], v[_], sz[_], cov[_], flip[_];
	#define lc(x) ch[x][0]
	#define rc(x) ch[x][1]
	bool isr (int x) { return (x == lc(fa[x]) || x == rc(fa[x])); }
	int idx (int x) { return x == rc(fa[x]); }
	void pushup (int x) { sz[x] = sz[lc(x)] + sz[rc(x)] + 1; }
	void rev (int x) { flip[x] ^= 1, swap(lc(x), rc(x)); }
	void pushdown (int x) {
		if (flip[x]) {
			flip[x] = 0;
			if (lc(x)) rev(lc(x));
			if (rc(x)) rev(rc(x));
		}
		if (cov[x]) {
			if (lc(x)) cov[lc(x)] = v[lc(x)] = cov[x];
			if (rc(x)) cov[rc(x)] = v[rc(x)] = cov[x];
			cov[x] = 0;
		}
	}
	void update (int x) { if (isr(x)) update(fa[x]); pushdown(x); }
	void rotate (int x) {
		int y = fa[x], z = fa[y], fp = idx(y), p = idx(x);
		if (isr(y)) ch[z][fp] = x; 
		ch[y][p] = ch[x][!p], ch[x][!p] = y;
		fa[y] = x, fa[x] = z;
		if (ch[y][p]) fa[ch[y][p]] = y;
		pushup(y), pushup(x);
	}
	void splay (int x) {
		update(x);
		while (isr(x)) {
			int y = fa[x];
			if (isr(y)) rotate(idx(y) == idx(x) ? y : x);
			rotate(x);
		} pushup(x);
	}
	void access (int x) {
		int lst = 0;
		for (int y = 0; x; x = fa[y = x]) {
			splay(x), rc(x) = y, pushup(x);
			tr.add(v[x], lst - sz[x]);
			lst = sz[x];
		}
	}
	void makeroot (int x, int col) {
		access(x), splay(x), rev(x);
		tr.add(col, sz[x]), 
		v[x] = cov[x] = col;
	}
}
using namespace LinkCutTree;
void dfs (int x, int pa) {
	sz[x] = 1, v[x] = x;
	for (int y : e[x]) if (y != pa) fa[y] = x, dfs(y, x);
}

string op;
int main () {
	//freopen("example.in", "r", stdin);
	//freopen("fk.out", "w", stdout);
	cin >> n >> m;
	tn = n;
	tr.clr();
	rep(i, 1, n - 1) {
		int x, y;
		scanf("%d%d", & x, & y);
		e[x].push_back(y), e[y].push_back(x);
	}
	dfs(1, 0);
	rep(i, 2, n) makeroot(i, i - 1);
	rep(i, 1, m) {
		cin >> op;
		int x, y;
		scanf("%d", & x);
		if (op[0] == 'c') {
			scanf("%d", & y);
			splay(x);
			int rnkx = sz[rc(x)] + 1 + tr.query(v[x] - 1);
			splay(y);
			int rnky = sz[rc(y)] + 1 + tr.query(v[y] - 1);
			if (rnkx < rnky) printf("%d\n", x);
			else printf("%d\n", y);
		} else if (op[0] == 'w') {
			splay(x);
			int rnk  = sz[rc(x)] + 1 + tr.query(v[x] - 1);
			printf("%d\n", rnk);
		} else makeroot(x, tn ++);
	}
	return 0;
}