题意：
给定一棵树，每条边有黑白两种颜色，初始都是白色，现在有三种操作：
1 u v：u到v路径（最短）上的边都取成相反的颜色
2 u v：u到v路径上相邻的边都取成相反的颜色（相邻即仅有一个节点在路径上）
3 u v：查询u到v路径上有多少个黑色边
思路：
对树进行树链剖分，分成重链和轻链，用两棵线段树W，L来维护。W维护树上在重链上的u和v之间的边的翻转情况（操作在线段树上的[pos[v],pos[u]]区间）
；L维护树上在重链上的u和v之间的相邻边的翻转情况
。那么某一个点u与它父亲节点fa[u]的边的最终翻转情况为：W(pos[u], pos[u])（如果边是重链上的边），W(pos[u], pos[u])^L(pos[fa[u]], pos[fa[u]])（如果边是轻链）。对于1操作，只要简单的在W上维护就可以了。对于2操作，除了在L上操作，还要注意头和尾的特殊处理（因为对于重链内的点，不包括头尾，只在W上查询），也就是u的重链上的儿子son[u]以及u的链头p=belong[u]要在W上翻转一次，结合图可能更能理解。还有就是线段树的操作了。
另外：
u可能没有son[u]，默认为虚点0，那么在线段树上需要加上一句话：if (l == r) return ;
#includeconst int N = 1e5 + 5;//线段树#define lson l, mid, o << 1#define rson mid + 1, r, o << 1 | 1struct Seg_Tree { int fp[N<<2], s[N<<2]; void flip(int l, int r, int o) { s[o] = (r - l + 1) - s[o]; fp[o] ^= 1; } void push_up(int o) { s[o] = s[o<<1] + s[o<<1|1]; } void push_down(int l, int r, int o) { if (fp[o]) { int mid = l + r >> 1; flip (lson); flip (rson); fp[o] = 0; } } void build(int l, int r, int o) { fp[o] = s[o] = 0; if (l == r) { return ; } int mid = l + r >> 1; build (lson); build (rson); } void updata(int ql, int qr, int l, int r, int o) { if (ql <= l && r <= qr) { flip (l, r, o); return ; } if (l == r) return ; //! push_down (l, r, o); int mid = l + r >> 1; if (ql <= mid) updata (ql, qr, lson); if (qr > mid) updata (ql, qr, rson); push_up (o); } int query(int ql, int qr, int l, int r, int o) { if (ql <= l && r <= qr) { return s[o]; } push_down (l, r, o); int mid = l + r >> 1, ret = 0; if (ql <= mid) ret += query (ql, qr, lson); if (qr > mid) ret += query (ql, qr, rson); push_up (o); return ret; }}W, L;std::vector edge[N];int sz[N], dep[N], son[N], fa[N];int pos[N], belong[N];int loc;int n;int query(int u, int v) { int p = belong[u], q = belong[v], ret = 0; while (p != q) { if (dep[p] < dep[q]) { std::swap (p, q); std::swap (u, v); } if (u != p) { ret += W.query (pos[son[p]], pos[u], 1, n, 1); } ret += (W.query (pos[p], pos[p], 1, n, 1) ^ L.query (pos[fa[p]], pos[fa[p]], 1, n, 1)); u = fa[p]; p = belong[u]; } if (u == v) return ret; if (dep[u] < dep[v]) { std::swap (u, v); } ret += W.query (pos[son[v]], pos[u], 1, n, 1); return ret;}void modify(int t, int u, int v) { int p = belong[u], q = belong[v]; while (p != q) { if (dep[p] < dep[q]) { std::swap (p, q); std::swap (u, v); } if (t == 1) { W.updata (pos[p], pos[u], 1, n, 1); } else { L.updata (pos[p], pos[u], 1, n, 1); W.updata (pos[son[u]], pos[son[u]], 1, n, 1); W.updata (pos[p], pos[p], 1, n, 1); } u = fa[p]; p = belong[u]; } if (dep[u] < dep[v]) { std::swap (u, v); } if (t == 1) { if (u == v) return ; W.updata (pos[son[v]], pos[u], 1, n, 1); } else { L.updata (pos[v], pos[u], 1, n, 1); W.updata (pos[son[u]], pos[son[u]], 1, n, 1); W.updata (pos[v], pos[v], 1, n, 1); }}//树链剖分void DFS2(int u, int chain) { pos[u] = ++loc; belong[u] = chain; if (son[u]) { DFS2 (son[u], chain); } for (auto v: edge[u]) { if (v == fa[u] || v == son[u]) continue; DFS2 (v, v); }}void DFS1(int u, int pa) { sz[u] = 1; dep[u] = dep[pa] + 1; son[u] = 0; fa[u] = pa; for (auto v: edge[u]) { if (v == pa) continue; DFS1 (v, u); sz[u] += sz[v]; if (sz[son[u]] < sz[v]) son[u] = v; }}void prepare() { sz[0] = dep[0] = fa[0] = 0; DFS1 (1, 0); loc = 0; DFS2 (1, 1); W.build (1, n, 1); L.build (1, n, 1);}void init_edge(int n) { for (int i=1; i<=n; ++i) { edge[i].clear (); }}int main() { int T; scanf ("%d", &T); while (T--) { scanf ("%d", &n); init_edge (n); for (int i=1; i