\(\text{Problem}\)

我们有一个树，大小为 \(n\)。

考虑树上的一条路径，如果一个边的两个点都在这路径上，我们称这个边属于这个路径，如果一个边有且只有一个点在这路径上，我们称这个边与这个路径相邻。

现在每个边要么是黑色的要么是白色的，一开始所有边都是白色的。

我们有 \(3\) 个操作，将某路径反色，将与某路径相邻的所有边反色，求一个路径上黑边的总数。

\(\text{Solution}\)

第二个操作有点难。。。

从查询上想办法，发现树链剖分查询时跳过 \(O(log)\) 条重链和 \(O(log)\) 条轻边

启示我们维护一个点向下的重边有没有被反色过，向下的所有轻边有没有被反色过

显然需要线段树的区间修改

然后试着看能不能把操作不重不漏的修改完

发现还需要一个标记数组维护一个点向上的轻边有没有被反色过

查询过轻边时要结合标记数组和线段树信息弄出它真实的颜色

细节比较多

\(\text{Code}\)

#include <cstdio>
#include <iostream>
#define RE register
#define IN inline
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;

const int N = 1e5 + 5;
int n, m, a[N], h[N], tot;
struct edge{int nxt, to;}e[N << 1];
IN void add(int x, int y){e[++tot] = edge{h[x], y}, h[x] = tot;}

int top[N], fa[N], dfn[N], siz[N], son[N], dep[N], dfc;
void dfs1(int x, int y)
{
    siz[x] = 1, fa[x] = y, dep[x] = dep[y] + 1;
    for(int i = h[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == y) continue;
        dfs1(v, x), siz[x] += siz[v];
        if (siz[son[x]] < siz[v]) son[x] = v;
    }
}
void dfs2(int x, int t)
{
    top[x] = t, dfn[x] = ++dfc;
    if (son[x]) dfs2(son[x], t);
    for(int i = h[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fa[x] || v == son[x]) continue;
        dfs2(v, v);
    }
}

int bz[N], sum[N * 4], tg1[N * 4], tg0[N * 4];
IN void push(int p, int l, int r){sum[p] = r - l + 1 - sum[p], tg1[p] ^= 1;}
IN void pushdown(int p, int l, int r)
{
    int mid = l + r >> 1;
    if (tg1[p]) push(ls, l, mid), push(rs, mid + 1, r), tg1[p] = 0;
    if (tg0[p]) tg0[ls] ^= tg0[p], tg0[rs] ^= tg0[p], tg0[p] = 0;
}
void Modify(int p, int l, int r, int tl, int tr, int v)
{
    if (tr < l || r < tl) return;
    if (tl <= l && r <= tr){if (v) push(p, l, r); else tg0[p] ^= 1; return;}
    pushdown(p, l, r);
    int mid = l + r >> 1;
    if (tl <= mid) Modify(ls, l, mid, tl, tr, v);
    if (tr > mid) Modify(rs, mid + 1, r, tl, tr, v);
    sum[p] = sum[ls] + sum[rs];
}
int Query(int p, int l, int r, int tl, int tr, int v)
{
    if (tr < l || r < tl) return 0;
    if (tl <= l && r <= tr) return (v ? sum[p] : tg0[p]);
    pushdown(p, l, r);
    int mid = l + r >> 1, res = 0;
    if (tl <= mid) res = Query(ls, l, mid, tl, tr, v);
    if (tr > mid) res += Query(rs, mid + 1, r, tl, tr, v);
    return res;
}

int main()
{
    scanf("%d", &n);
    for(RE int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
    dfs1(1, 0), dfs2(1, 1), scanf("%d", &m);
    for(RE int x, y, t, fx, fy; m; --m)
    {
        scanf("%d%d%d", &t, &x, &y), fx = top[x], fy = top[y];
        if (t == 1)
        {
            while (fx ^ fy)
                if (dep[fx] > dep[fy]) Modify(1, 1, n, dfn[fx], dfn[x] - 1, 1), bz[fx] ^= 1, x = fa[fx], fx = top[x];
                else Modify(1, 1, n, dfn[fy], dfn[y] - 1, 1), bz[fy] ^= 1, y = fa[fy], fy = top[y];
            if (x == y) continue;
            if (dep[x] > dep[y]) swap(x, y); Modify(1, 1, n, dfn[x], dfn[y] - 1, 1);
        }
        else if (t == 2){
            while (fx ^ fy)
                if (dep[fx] > dep[fy])
                    Modify(1, 1, n, dfn[fx], dfn[x], 0), Modify(1, 1, n, dfn[x], dfn[x], 1), bz[fx] ^= 1, x = fa[fx], fx = top[x];
                else Modify(1, 1, n, dfn[fy], dfn[y], 0), Modify(1, 1, n, dfn[y], dfn[y], 1), bz[fy] ^= 1, y = fa[fy], fy = top[y];
            if (dep[x] > dep[y]) swap(x, y); Modify(1, 1, n, dfn[x], dfn[y], 0), Modify(1, 1, n, dfn[y], dfn[y], 1);
            if (x == top[x]) bz[x] ^= 1; else Modify(1, 1, n, dfn[fa[x]], dfn[fa[x]], 1);
        }
        else{
            t = 0;
            while (fx ^ fy)
                if (dep[fx] > dep[fy])
                    t += Query(1, 1, n, dfn[fx], dfn[x] - 1, 1) + (bz[fx] ^ Query(1, 1, n, dfn[fa[fx]], dfn[fa[fx]], 0)), x = fa[fx], fx = top[x];
                else t += Query(1, 1, n, dfn[fy], dfn[y] - 1, 1) + (bz[fy] ^ Query(1, 1, n, dfn[fa[fy]], dfn[fa[fy]], 0)), y = fa[fy], fy = top[y];
            if (x ^ y && dep[x] > dep[y]) swap(x, y); t += Query(1, 1, n, dfn[x], dfn[y] - 1, 1);
            printf("%d\n", t);
        }
    }
}