树剖求条

球球啦

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2.5e5 + 10;
inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-'){w = -1;} ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = (s << 3) + (s << 1) + (ch ^ 48); ch = getchar();}
    return s * w;
}
int head[N], ne[N << 1], to[N << 1], id;
int n, m;
void add(int x, int y){to[++id] = y, ne[id] = head[x], head[x] = id;}
int son[N], siz[N];
int fa[N], dep[N], top[N];
int dn, dfn[N];
void dfs1(int u, int faa)
{
    dep[u] = dep[faa] + 1;
    fa[u] = faa;
    siz[u] = 1;
    for(int i = head[u]; i; i = ne[i])
    {
        int v = to[i];
        if(v == faa) continue;
        dfs1(v, u);
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int tp)
{
    top[u] = tp;
    dfn[u] = ++dn;
    if(!son[u]) return ;
    dfs2(son[u], tp);
    for(int i = head[u]; i; i = ne[i])
    {
        int v = to[i];
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
struct node
{
    int l, r;
    int sum;
    int col;
}tr[N << 2];
void push_up(int u){tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;}
void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    // tr[u].col = -1;
    if(l == r) return tr[u].sum = 1, void();
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}
void change(int u, int l)
{
    if(l == tr[u].l && tr[u].r == l)
    {
        // tr[u].col = 0;
        tr[u].sum = 0;
        return ;
    }
    // push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) change(u << 1, l);
    else change(u << 1 | 1, l);
    push_up(u);
}
int query(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    // push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int ans = 0;
    if(l <= mid) ans += query(u << 1, l, r);
    if(mid < r) ans += query(u << 1 | 1, l, r);
    return ans;
}
signed main()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int x=  read(), y = read();
        if(x > y) swap(x, y);
        add(x, y);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    cin >> m;
    for(int i = 1; i <= n + m - 1; i++)
    {
        char opt;
        int x, y;
        cin >> opt;
        x = read();
        if(opt == 'A')
        {
            y = read();
            if(dfn[x] < dfn[y]) swap(x, y);
            change(1, dfn[x]);
            // change_way(x, y);
        }
        if(opt == 'W')
        {
            y = 1;
            int ans = 0;
            while(top[x] != top[y])
            {
                // if(dep[top[x]] < dep[top[y]]) swap(x, y);
                ans += query(1, dfn[top[x]], dfn[x]);
                x = fa[top[x]];
            }
            // if(dfn[x] > dfn[y]) swap(x, y);
            ans += query(1, 1, dfn[x]) - 1;
            printf("%lld\n", ans);
        }
    }
    return 0;
}