[Sdoi2017]树点涂色
题意：一棵有根树，支持x到根染成新颜色，求x到y颜色数，求x子树里点到根颜色数最大值
考场发现这个信息是可减的，但是没想到lct
特意设计成lct的形式！
如何求颜色数？
维护一个点和父亲的颜色是否一样，不一样为1，就是前缀和。考虑相邻的思想和那道“水位线”有点像
x到y的答案就是\(S_x + S_y - 2*S_{lca} + 1\)
一个点到根染新颜色，对应了lct的access操作，重边就是一样轻边就是不一样，修改轻重边就是子树加，其他两个操作单点求值，子树求最大值。用线段树维护dfs序
实现上注意：
- access过程中，不能直接修改rc和y，因为splay的形态是不断变化的，应该修改它们所在的splay代表的原树的根
- 并且要先把rc与x重边切断再找根
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N=1e5+5;
#define fir first
#define sec second
inline int read() {
char c=getchar(); int x=0, f=1;
while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
}
int n, Q, op, x, y;
struct edge{int v, ne;} e[N<<1];
int cnt=1, h[N];
inline void ins(int u, int v) {
e[++cnt]=(edge){v, h[u]}; h[u]=cnt;
e[++cnt]=(edge){u, h[v]}; h[v]=cnt;
}
int fa[N], deep[N], size[N], mx[N], top[N], dfc, ver[N];
pair<int, int> dfn[N];
void dfs(int u) {
size[u]=1;
for(int i=h[u];i;i=e[i].ne)
if(e[i].v != fa[u]) {
int v=e[i].v;
fa[v] = u; deep[v] = deep[u]+1;
dfs(v);
size[u] += size[v];
if(size[v] > size[mx[u]]) mx[u] = v;
}
}
void dfs(int u, int anc) {
dfn[u].fir = ++dfc; ver[dfc] = u;
top[u] = anc;
if(mx[u]) dfs(mx[u], anc);
for(int i=h[u];i;i=e[i].ne)
if(e[i].v != fa[u] && e[i].v != mx[u]) dfs(e[i].v, e[i].v);
dfn[u].sec = dfc;
}
inline int lca(int x, int y) {
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return deep[x] < deep[y] ? x : y;
}
namespace seg {
#define mid ((l+r)>>1)
#define lc x<<1
#define rc x<<1|1
#define lson lc, l, mid
#define rson rc, mid+1, r
struct meow{int tag, max;} t[N<<2];
inline void paint(int x, int v) {
t[x].tag += v; t[x].max += v;
}
inline void pushdn(int x) {
if(t[x].tag) {
paint(lc, t[x].tag);
paint(rc, t[x].tag);
t[x].tag = 0;
}
}
inline void merge(int x) {t[x].max = max(t[lc].max, t[rc].max);}
void build(int x, int l, int r) {
if(l == r) t[x].max = deep[ ver[l] ] + 1;
else build(lson), build(rson), merge(x);
}
void add(int x, int l, int r, int ql, int qr, int v) {
if(ql<=l && r<=qr) paint(x, v);
else {
pushdn(x);
if(ql <= mid) add(lson, ql, qr, v);
if(mid < qr ) add(rson, ql, qr, v);
merge(x);
}
}
int que(int x, int l, int r, int p) {
if(l == r) return t[x].max;
else {
pushdn(x);
if(p <= mid) return que(lson, p);
else return que(rson, p);
}
}
int que(int x, int l, int r, int ql, int qr) {
if(ql<=l && r<=qr) return t[x].max;
else {
pushdn(x);
int ans=0;
if(ql <= mid) ans = max(ans, que(lson, ql, qr));
if(mid < qr ) ans = max(ans, que(rson, ql, qr));
return ans;
}
}
#undef lc
#undef rc
}
inline void addsub(int u, int val) {
seg::add(1, 1, n, dfn[u].fir, dfn[u].sec, val);
}
inline void quer(int x, int y) {
int p = lca(x, y);
int ans = seg::que(1, 1, n, dfn[x].fir) + seg::que(1, 1, n, dfn[y].fir) - 2 * seg::que(1, 1, n, dfn[p].fir) + 1;
printf("%d\n", ans);
}
inline void qmax(int x) {
int ans = seg::que(1, 1, n, dfn[x].fir, dfn[x].sec);
printf("%d\n", ans);
}
namespace lct {
#define lc t[x].ch[0]
#define rc t[x].ch[1]
#define pa t[x].fa
struct meow{int ch[2], fa;} t[N];
int sz;
inline int wh(int x) {return t[pa].ch[1] == x;}
inline int isr(int x) {return t[pa].ch[0] != x && t[pa].ch[1] != x;}
inline void rotate(int x) {
int f=t[x].fa, g=t[f].fa, c=wh(x);
if(!isr(f)) t[g].ch[wh(f)] = x; t[x].fa = g;
t[f].ch[c] = t[x].ch[c^1]; t[ t[f].ch[c] ].fa = f;
t[x].ch[c^1] = f; t[f].fa = x;
}
inline void splay(int x) {
for(; !isr(x); rotate(x))
if(!isr(pa)) rotate(wh(x) == wh(pa) ? pa : x);
}
inline int findr(int x) {
splay(x); while(lc) x=lc; splay(x);
return x;
}
void access(int x) {
for(int y=0; x; y=x, x=pa) {
splay(x);
if(rc) {
int u=rc; rc=0;
u=findr(u), addsub(u, 1);
}
if(y) y=findr(y), addsub(y, -1);
rc=y;
}
}
void init() {for(int i=1; i<=n; i++) t[i].fa = fa[i];}
}
int main() {
//freopen("in", "r", stdin);
freopen("paint.in", "r", stdin);
freopen("paint.out", "w", stdout);
n=read(); Q=read();
for(int i=1; i<n; i++) ins(read(), read());
dfs(1); dfs(1, 1); seg::build(1, 1, n); lct::init();
//for(int i=1; i<=n; i++) printf("%d ", ver[i]); puts(" ver");
for(int i=1; i<=Q; i++) {
op=read(); x=read();
if(op==1) lct::access(x);
else if(op==2) y=read(), quer(x, y);
else qmax(x);
}
}