P7735 [NOI2021] 轻重边
大意
给定两个点 \(a\) 和 \(b\)，首先对于 \(a\) 到 \(b\) 路径上的所有点 \(x\)（包含 \(a\) 和 \(b\)），你要将与 \(x\) 相连的所有边变为轻边。然后再将 \(a\) 到 \(b\) 路径上包含的所有边变为重边。
给定两个点 \(a\) 和 \(b\)，你需要计算当前 \(a\) 到 \(b\) 的路径上一共包含多少条重边。
思路
我们考虑一个小巧思。
我们将问题可以转化为将 \(a \to b\) 这条路径的点染上独一无二的颜色，最终求 \(a \to b\) 路径上的重边即为两端颜色相同的边的数量。
因为每次我们选的颜色都不一样，这样操作一定能够让我们通过只记录端点的颜色去统计这个值，我们通过直接维护区间的左右的端点的颜色和相邻重色的个数，我们如果区间的端点颜色重合就可以将这个答案继续累加。这个就是处理本题线段树的方式。
但是对于这个题目是在树上的操作，那就没什么说的了，直接树剖维护即可。但是如果你像我一样闲着没事的话可以用 LCT 维护，原因是这个更改 \(a \to b\) 路径的过程可以用 LCT 的 split 操作非常简便的完成。至于 LCT 里面维护的内容，和线段树几乎一样，剩下就没什么了。
代码
#include<iostream>
#include<algorithm>
using namespace std;#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;struct node{int ch[2], fa;int col, tag;int lc, rc;int cnt; int sz;bool rev;node(){ch[1] = ch[0] = fa = 0;col = tag = lc = rc = cnt = sz = 0;rev = false;}
}t[MAXN];bool isroot(int x){return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}void pushup(int x) {t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;t[x].cnt = t[lc(x)].cnt + t[rc(x)].cnt;t[x].lc = lc(x) ? t[lc(x)].lc : t[x].col;t[x].rc = rc(x) ? t[rc(x)].rc : t[x].col;if(lc(x) && t[lc(x)].rc == t[x].col) t[x].cnt ++;if(rc(x) && t[rc(x)].lc == t[x].col) t[x].cnt ++;
}void update_rev(int x){if(!x) return;swap(lc(x), rc(x));swap(t[x].lc, t[x].rc);t[x].rev ^= 1;
}void apply_col(int x, int c){if(!x) return;t[x].col = t[x].lc = t[x].rc = t[x].tag = c;t[x].cnt = t[x].sz - 1;
}void pushdown(int x){if(t[x].rev){update_rev(lc(x));update_rev(rc(x));t[x].rev = 0;}if(t[x].tag){apply_col(lc(x), t[x].tag);apply_col(rc(x), t[x].tag);t[x].tag = 0;}
}void rotate(int x){int y = fa(x), z = fa(y);int k = (rc(y) == x);if(!isroot(y)) t[z].ch[rc(z) == y] = x;fa(x) = z;t[y].ch[k] = t[x].ch[k ^ 1];if (t[x].ch[k ^ 1]) fa(t[x].ch[k ^ 1]) = y;t[x].ch[k ^ 1] = y;fa(y) = x;pushup(y);pushup(x);
}void pushshell(int x){if(!isroot(x)) pushshell(fa(x));pushdown(x);
}void splay(int x){pushshell(x);while(!isroot(x)){int y = fa(x), z = fa(y);if(!isroot(y)) (rc(z) == y) ^ (rc(y) == x) ? rotate(x) : rotate(y);rotate(x);}
}void access(int x){for(int y = 0;x;y = x, x = fa(x)){splay(x);rc(x) = y;pushup(x);}
}void makeroot(int x){access(x);splay(x);update_rev(x);
}void split(int x, int y){makeroot(x);access(y);splay(y);
}void modify(int u, int v, int c){split(u, v);apply_col(v, c);
}void solve(){int n, m; cin >> n >> m;for(int i = 1;i <= n;i ++){t[i] = node();t[i].col = t[i].lc = t[i].rc = -i;t[i].sz = 1;}for(int i = 1;i < n;i ++){int u, v; cin >> u >> v;makeroot(u); fa(u) = v;}int cur_col = 0;while(m --){int op, u, v;cin >> op >> u >> v;if(op == 1){modify(u, v, ++ cur_col);split(u, v);apply_col(v, ++ cur_col);}else{split(u, v);cout << t[v].cnt << "\n";}}
}int main(){ios::sync_with_stdio(0);cin.tie(0);int T; cin >> T;while(T --) solve();return 0;
}