题意：

解：

发现我们每次染的都是不同的颜色，那么用lct维护的话一个颜色就会在一个splay里。染色是access。

维护每个节点到根路径上的虚边数量。

虚边的切换只会在access和link中出现。于是access的时候顺便修改那个子树。lct上啥也不用维护。

查询链可以用两端点减去lca。

1 #include 
      
         2   3 const int N = 100010, INF = 0x3f3f3f3f;  4   5 struct Edge {  6     int nex, v;  7 }edge[N << 1]; int tp;  8   9 int e[N], n, siz[N], pos[N], id[N], d[N], num, top[N], father[N], son[N]; /// tree 10 int fa[N], s[N][2], stk[N], Top; /// lct 11 bool rev[N]; 12 int large[N << 2], tag[N << 2]; /// seg 13  14 inline void add(int x, int y) { 15     tp++; 16     edge[tp].v = y; 17     edge[tp].nex = e[x]; 18     e[x] = tp; 19     return; 20 } 21  22 void DFS_1(int x, int f) { /// father siz son d 23     siz[x] = 1; 24     fa[x] = father[x] = f; 25     for(int i = e[x]; i; i = edge[i].nex) { 26         int y = edge[i].v; 27         if(y == f) continue; 28         d[y] = d[x] + 1; 29         DFS_1(y, x); 30         siz[x] += siz[y]; 31         if(siz[y] > siz[son[x]]) { 32             son[x] = y; 33         } 34     } 35     return; 36 } 37  38 void DFS_2(int x, int f) { /// top id pos 39     top[x] = f; 40     pos[x] = ++num; 41     id[num] = x; 42     if(son[x]) DFS_2(son[x], f); 43     for(int i = e[x]; i; i = edge[i].nex) { 44         int y = edge[i].v; 45         if(y == father[x] || y == son[x]) continue; 46         DFS_2(y, y); 47     } 48     return; 49 } 50  51 inline void Pushdown(int o) { 52     if(tag[o]) { 53         int ls = o << 1, rs = o << 1 | 1; 54         tag[ls] += tag[o]; 55         tag[rs] += tag[o]; 56         large[ls] += tag[o]; 57         large[rs] += tag[o]; 58         tag[o] = 0; 59     } 60     return; 61 } 62  63 void build(int l, int r, int o) { 64     if(l == r) { 65         large[o] = d[id[r]]; 66         return; 67     } 68     int mid = (l + r) >> 1; 69     build(l, mid, o << 1); 70     build(mid + 1, r, o << 1 | 1); 71     large[o] = std::max(large[o << 1], large[o << 1 | 1]); 72     return; 73 } 74  75 void add(int L, int R, int v, int l, int r, int o) { 76     if(L <= l && r <= R) { 77         large[o] += v; 78         tag[o] += v; 79         return; 80     } 81     Pushdown(o); 82     int mid = (l + r) >> 1; 83     if(L <= mid) add(L, R, v, l, mid, o << 1); 84     if(mid < R) add(L, R, v, mid + 1, r, o << 1 | 1); 85     large[o] = std::max(large[o << 1], large[o << 1 | 1]); 86     return; 87 } 88  89 int getMax(int L, int R, int l, int r, int o) { 90     if(L <= l && r <= R) return large[o]; 91     int mid = (l + r) >> 1, ans = -INF; 92     Pushdown(o); 93     if(L <= mid) ans = std::max(ans, getMax(L, R, l, mid, o << 1)); 94     if(mid < R) ans = std::max(ans, getMax(L, R, mid + 1, r, o << 1 | 1)); 95     return ans; 96 } 97  98 int ask(int p, int l, int r, int o) { 99     if(l == r) return large[o];100     Pushdown(o);101     int mid = (l + r) >> 1;102     if(p <= mid) return ask(p, l, mid, o << 1);103     else return ask(p, mid + 1, r, o << 1 | 1);104 }105 106 inline void pushdown(int x) {107     if(rev[x]) {108         std::swap(s[x][0], s[x][1]);109         if(s[x][0]) rev[s[x][0]] ^= 1;110         if(s[x][1]) rev[s[x][1]] ^= 1;111         rev[x] = 0;112     }113     return;114 }115 116 inline void pushup(int x) {117     return;118 }119 120 inline bool no_root(int x) {121     return (s[fa[x]][0] == x) || (s[fa[x]][1] == x);122 }123 124 inline void rotate(int x) {125     int y = fa[x];126     int z = fa[y];127     bool f = (s[y][1] == x);128 129     fa[x] = z;130     if(no_root(y)) {131         s[z][s[z][1] == y] = x;132     }133     s[y][f] = s[x][!f];134     if(s[x][!f]) {135         fa[s[x][!f]] = y;136     }137     s[x][!f] = y;138     fa[y] = x;139 140     pushup(y);141     return;142 }143 144 inline void splay(int x) {145     int y = x;146     stk[++Top] = y;147     while(no_root(y)) {148         y = fa[y];149         stk[++Top] = y;150     }151     while(Top) {152         pushdown(stk[Top]);153         Top--;154     }155 156     y = fa[x];157     int z = fa[y];158     while(no_root(x)) {159         if(no_root(y)) {160             (s[z][1] == y) ^ (s[y][1] == x) ?161             rotate(x) : rotate(y);162         }163         rotate(x);164         y = fa[x];165         z = fa[y];166     }167     pushup(x);168     return;169 }170 171 inline void change(int x, int v) {172     pushdown(x);173     while(s[x][0]) {174         x = s[x][0];175         pushdown(x);176     }177     /// x178     add(pos[x], pos[x] + siz[x] - 1, v, 1, n, 1);179     return;180 }181 182 inline void access(int x) {183     int y = 0;184     while(x) {185         splay(x);186         if(s[x][1]) change(s[x][1], 1);187         if(y) change(y, -1);188         s[x][1] = y;189         pushup(x);190         y = x;191         x = fa[x];192     }193     return;194 }195 196 inline int lca(int x, int y) {197     while(top[x] != top[y]) {198         if(d[top[x]] < d[top[y]]) {199             y = father[top[y]];200         }201         else {202             x = father[top[x]];203         }204     }205     return d[x] < d[y] ? x : y;206 }207 208 inline int ask(int x, int y) {209     //printf("ask : %d %d lca %d \n", x, y, lca(x, y));210     //printf("ask : %d + %d - 2 * %d \n", ask(pos[x], 1, n, 1), ask(pos[y], 1, n, 1), ask(pos[lca(x, y)], 1, n, 1));211     return ask(pos[x], 1, n, 1) + ask(pos[y], 1, n, 1) - 2 * ask(pos[lca(x, y)], 1, n, 1);212 }213 214 inline int query(int x) {215     return getMax(pos[x], pos[x] + siz[x] - 1, 1, n, 1);216 }217 218 int main() {219     int m;220     scanf("%d%d", &n, &m);221     for(int i = 1, x, y; i < n; i++) {222         scanf("%d%d", &x, &y);223         add(x, y); add(y, x);224     }225     /// init226     DFS_1(1, 0);227     DFS_2(1, 1);228     build(1, n, 1);229 230     for(int i = 1, f, x, y; i <= m; i++) {231         scanf("%d%d", &f, &x);232         if(f == 1) { /// change233             access(x);234         }235         else if(f == 2) {236             scanf("%d", &y);237             printf("%d\n", ask(x, y) + 1);238         }239         else { /// f == 3240             printf("%d\n", query(x) + 1);241         }242     }243     return 0;244 }