LCT + 树剖 + 线段树。

由于每个操作都是从一个点染到根，那么就可以很清楚的知道：颜色种数 = 颜色段数。

接着我们可以知道两个点\(x,y\)的颜色种数其实就是\(x\)到根的颜色种数 + \(y\)到根的颜色种数 - \(2lca(x,y)\)到根的颜色种数 + 1。

将一个点染色时，同时会不可避免的断掉一些颜色段，使断掉的部分子树的答案会加1。

我们用\(\text{LCT}\)来维护这些链。

通过把图画出来可以知道：

增加1的子树其实是access时原来的右儿子，

而减少1其实是access时像现在的右儿子。

之后就可以做了。

#include 
    
     #define _swap(a,b) (a ^= b ^= a ^= b)const int maxn = 1e5 + 10;class FastIO {    private:        #define tn(x) (x << 1) + (x << 3)        #define D isdigit(c = getchar())        char c;  int T, S[10000];    public:        template
     
       inline void read(Tp& x) { x = 0;  while(!D);  while(x = tn(x) + (c & 15),D); }        template
      
        inline void write(Tp x) { while(S[++T] = x % 10 + 48,x /= 10);  while(T) putchar(S[T--]); }        template
       
         inline void read(Tp& x,Ar&... y) { read(x);  read(y...); }        template
        
          inline void writeln(const Tp& x) { write(x);  putchar('\n'); }} I;inline void cmax(int& x,int y) { if(x < y) x = y; }inline int _max(int x,int y) { return x > y ? x : y; }int n, m, i, j, k, cnte, tot;int fa[maxn], id[maxn], dep[maxn], sz[maxn], dfn[maxn], top[maxn], hson[maxn];struct edge {    int v;    edge* nxt;} pool[maxn << 1], *head[maxn], *cur = pool;inline void adde(int u,int v) {    edge* p = cur++;    p -> v = v;  p -> nxt = head[u];    head[u] = p;}void dfs1(int u,int pa) {    dep[u] = dep[pa] + 1;  fa[u] = pa;  sz[u] = 1;    for(edge* p = head[u];p;p = p -> nxt) {        int v = p -> v;        if(v == pa)            continue;        dfs1(v,u);        sz[u] += sz[v];        if(sz[v] > sz[ hson[u] ])            hson[u] = v;    }}void dfs2(int u,int up) {    top[u] = up;  dfn[u] = ++tot;  id[tot] = u;    if(hson[u])        dfs2(hson[u],up);    for(edge* p = head[u];p;p = p -> nxt) {        int v = p -> v;        if(v == fa[u] || v == hson[u])            continue;        dfs2(v,v);    }}inline int Glca(int u,int v) {    while(top[u] != top[v]) {        if(dep[ top[u] ] < dep[ top[v] ])            _swap(u,v);        u = fa[ top[u] ];    }    return dep[u] < dep[v] ? u : v;}class Segment_Tree {    private:        int mx[maxn << 2], tag[maxn << 2];    public:        inline void push_up(int u) {            mx[u] = _max(mx[u << 1],mx[u << 1 | 1]);        }        inline void push_down(int u) {            if(!tag[u])                return;            mx[u << 1] += tag[u];  mx[u << 1 | 1] += tag[u];            tag[u << 1] += tag[u];  tag[u << 1 | 1] += tag[u];            tag[u] = 0;        }        void build(int l,int r,int u) {            if(l == r)                return mx[u] = dep[ id[l] ], void();            int mid = (l + r) >> 1;            build(l,mid,u << 1);            build(mid + 1,r,u << 1 | 1);            push_up(u);        }        int query(int ql,int qr,int l,int r,int u) {            //printf("%d %d %d %d %d %d\n",ql,qr,l,r,u,mx[u]);            if(ql <= l && r <= qr)                return mx[u];            push_down(u);            int res = 0, mid = (l + r) >> 1;            if(ql <= mid)                cmax(res,query(ql,qr,l,mid,u << 1));            if(mid < qr)                cmax(res,query(ql,qr,mid + 1,r,u << 1 | 1));            return res;        }        void modify(int ml,int mr,int l,int r,int u,int x) {            if(ml <= l && r <= mr)                return tag[u] += x, mx[u] += x, void();            push_down(u);            int mid = (l + r) >> 1;            if(ml <= mid)                modify(ml,mr,l,mid,u << 1,x);            if(mid < mr)                modify(ml,mr,mid + 1,r,u << 1 | 1,x);            push_up(u);            return;        }} segt;class Link_Cut_Tree {    private:        int ch[maxn][2];    public:        int fa[maxn];        inline bool nroot(int u) {            return ch[ fa[u] ][0] == u || ch[ fa[u] ][1] == u;        }        inline int ident(int u) {            return ch[ fa[u] ][1] == u;        }        inline void rotate(int u) {            int oldf = fa[u], oldgf = fa[oldf], whi = ident(u);            if(nroot(oldf))                ch[oldgf][ident(oldf)] = u;            ch[oldf][whi] = ch[u][whi ^ 1];            fa[ ch[oldf][whi] ] = oldf;            ch[u][whi ^ 1] = oldf;            fa[oldf] = u;  fa[u] = oldgf;        }        inline void splay(int u) {            for(int p = fa[u];nroot(u);rotate(u),p = fa[u]) {                if(nroot(p))                    rotate(ident(p) == ident(u) ? p : u);            }        }        inline int find_root(int x) {            while(ch[x][0])                x = ch[x][0];            return x;        }        inline void access(int x) {            for(int y = 0, z;x;x = fa[y = x]) {                splay(x);                if(ch[x][1])                    z = find_root(ch[x][1]), segt.modify(dfn[z],dfn[z] + sz[z] - 1,1,n,1,1);                if(ch[x][1] = y)                    z = find_root(ch[x][1]), segt.modify(dfn[z],dfn[z] + sz[z] - 1,1,n,1,-1);            }        }} lct;int main() {    I.read(n,m);    for(int i = 1, u, v;i < n;i++) {        I.read(u,v);        adde(u,v);        adde(v,u);    }    dfs1(1,0);    dfs2(1,1);    for(int i = 1;i <= n;i++)        lct.fa[i] = fa[i];    segt.build(1,n,1);    for(int op, x, y;m;m--) {        I.read(op,x);        if(op == 1)            lct.access(x);        else if(op == 2) {            I.read(y);            int z = Glca(x,y);            printf("%d\n",segt.query(dfn[x],dfn[x],1,n,1) + segt.query(dfn[y],dfn[y],1,n,1) - 2 * segt.query(dfn[z],dfn[z],1,n,1) + 1);        } else            printf("%d\n",segt.query(dfn[x],dfn[x] + sz[x] - 1,1,n,1));    }    return 0;}