哈人*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;
}