哦代码粘的不是最新版（）。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define pii pair<int,int>
#define p1(x) (x).first
#define p2(x) (x).second
int n, q;
int C[200300];
int xc[200300];
vector<int>g[100300];
int d[100300], f[100300], tp[100300], dfn[100300], siz[100300], loc[100300], hs[100300];
map<int, int>mp[100300];
struct node {
int s, lid, rid, mx, cnt, tgmx, tgid;
friend node operator +(const node A, const node B) {
if (A.s == -1)
return B;
if (B.s == -1)
return A;
return {A.s + B.s, A.lid, B.rid, max(A.mx, B.mx), A.cnt + B.cnt - (A.rid == B.lid), 0, 0};
}
inline void add_mx(int x) {
tgmx += x;
mx += x;
}
inline void cover_id(int x) {
tgid = x;
lid = rid = x;
cnt = 1;
}
} T[100300 << 2];
inline void upd(int x) {
T[x] = T[lc(x)] + T[rc(x)];
}
inline void pd(int x) {
if (T[x].tgmx) {
T[lc(x)].add_mx(T[x].tgmx);
T[rc(x)].add_mx(T[x].tgmx);
T[x].tgmx = 0;
}
if (T[x].tgid) {
T[lc(x)].cover_id(T[x].tgid);
T[rc(x)].cover_id(T[x].tgid);
T[x].tgid = 0;
}
}
int col = 0;
inline void bd(int x, int l, int r) {
if (l == r) {
T[x] = {1, loc[l], loc[l], d[loc[l]], 1, 0, 0};
return ;
}
int mid = l + r >> 1;
bd(lc(x), l, mid);
bd(rc(x), mid + 1, r);
upd(x);
}
inline void cov(int x, int l, int r, int L, int R, int c) {
if (L <= l && r <= R) {
T[x].cover_id(c);
return ;
}
pd(x);
int mid = l + r >> 1;
if (L <= mid)
cov(lc(x), l, mid, L, R, c);
if (R > mid)
cov(rc(x), mid + 1, r, L, R, c);
upd(x);
}
inline void add(int x, int l, int r, int L, int R, int c) {
if (L <= l && r <= R) {
T[x].add_mx(c);
return ;
}
pd(x);
int mid = l + r >> 1;
if (L <= mid)
add(lc(x), l, mid, L, R, c);
if (R > mid)
add(rc(x), mid + 1, r, L, R, c);
upd(x);
}
queue<int>Q;
inline node gt(int x, int l, int r, int L, int R) {
if (L <= l && r <= R)
return T[x];
pd(x);
int mid = l + r >> 1;
bool lp = L <= mid, rp = R > mid;
if (lp && rp)
return gt(lc(x), l, mid, L, R) + gt(rc(x), mid + 1, r, L, R);
if (lp)
return gt(lc(x), l, mid, L, R);
if (rp)
return gt(rc(x), mid + 1, r, L, R);
assert(0);
}
inline void ADD(int x, int k) {
// cout<<x<<" "<<k<<endl;
// if(k==1){
// cout<<x<<" ";
// }
// else cout<<"!"<<endl;
add(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, k);
// if(k==1){
// cout<<gt(1,1,n,dfn[791],dfn[791]).mx<<endl;
// }
}
inline void ers(int x, int l, int r, int L, int R) {
if (T[x].s == 0)
return ;
if (l == r) {
T[x].s = 0;
Q.push(loc[l]);
return ;
}
pd(x);
int mid = l + r >> 1;
if (L <= mid)
ers(lc(x), l, mid, L, R);
if (R > mid)
ers(rc(x), mid + 1, r, L, R);
upd(x);
}
inline void ins(int x, int l, int r, int c) {
if (l == r) {
if (T[x].s)
return ;
T[x].s = 1;
return ;
}
pd(x);
int mid = l + r >> 1;
if (c <= mid)
ins(lc(x), l, mid, c);
else
ins(rc(x), mid + 1, r, c);
upd(x);
}
int tk;
inline void dfs(int u) {
siz[u] = 1;
d[u] = d[f[u]] + 1;
for (int v : g[u])
if (v != f[u]) {
f[v] = u;
dfs(v);
siz[u] += siz[v];
if (siz[v] > siz[hs[u]])
hs[u] = v;
}
}
inline void dfs(int u, int t) {
tp[u] = t;
loc[dfn[u] = ++tk] = u;
if (hs[u])
dfs(hs[u], t);
for (int v : g[u])
if (v != f[u] && v != hs[u])
dfs(v, v);
for (int v : g[u])
if (v != f[u])
mp[u][dfn[v] + siz[v] - 1] = v;
}
inline node rev(node A) {
swap(A.lid, A.rid);
return A;
}
inline int LCA(int x, int y) {
while (tp[x] != tp[y]) {
if (d[tp[x]] < d[tp[y]])
swap(x, y);
x = f[tp[x]];
}
if (d[x] < d[y])
swap(x, y);
return y;
}
inline void mod(int x, int c) {
xc[c] = x;
while (x) {
cov(1, 1, n, dfn[tp[x]], dfn[x], c);
ers(1, 1, n, dfn[tp[x]], dfn[x]);
x = f[tp[x]];
}
ADD(1, 1);
ins(1, 1, n, dfn[1]);
C[1] = c;
x = xc[c];
while (!Q.empty()) {
int lc = Q.front(), c = C[lc];
Q.pop();
ADD(lc, -1);
int L = LCA(x, xc[c]);
if (L == xc[c]) {
xc[c] = -1;
continue;
}
L = mp[L].lower_bound(dfn[xc[c]])->second;
// cout<<c<<" ";
C[L] = c;
ins(1, 1, n, dfn[L]);
}
}
inline node gt(int x, int y) {
node X, Y;
X.s = Y.s = -1;
while (tp[x] != tp[y]) {
if (d[tp[x]] > d[tp[y]]) {
X = X + rev(gt(1, 1, n, dfn[tp[x]], dfn[x]));
x = f[tp[x]];
} else {
Y = gt(1, 1, n, dfn[tp[y]], dfn[y]) + Y;
y = f[tp[y]];
}
}
if (d[x] > d[y])
X = X + rev(gt(1, 1, n, dfn[y], dfn[x]));
else
Y = gt(1, 1, n, dfn[x], dfn[y]) + Y;
return X + Y;
}
signed main() {
freopen("paint1.in","r",stdin);
// freopen("yoimiya.out","w",stdout);
ios::sync_with_stdio(0);
cin >> n >> q;
col = n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1);
dfs(1, 1);
for (int i = 1; i <= n; i++)
xc[i] = i, C[i] = i;
bd(1, 1, n);
// cout<<siz[1]<<endl;
// cout<<d[LCA(816,791)]<<endl;
// cout<<d[791]<<endl;
//return 0;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x;
cin >> x;
mod(x, ++col);
} else if (op == 2) {
int x, y;
cin >> x >> y;
cout << gt(x, y).cnt << endl;
} else {
int x;
cin >> x;
cout << gt(1, 1, n, dfn[x], dfn[x] + siz[x] - 1).mx << endl;
}
}
cout.flush();
return 0;
}
/*
5 2
1 2
2 3
3 4
3 5
1 4
3 3
*/
```
by Ranger_HoFr @ 2024-02-25 17:18:59