WA 10pts 求条

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n , m , x[N] , y[N] , fa[N] , dep[N];
int siz[N] , son[N] , top[N] , dfn[N] , pos[N] , low[N] , num = 0;
int sum[N << 2];
bool tag[N << 2];
bool vis[N];
struct opt {int op , a , b;} o[N]; int tot = 0;
map <pair<int , int> , bool> del;
vector<int> g[N];

int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

void dfs1(int u , int pre)
{
    siz[u] = 1;
    fa[u] = pre;
    dep[u] = dep[pre] + 1;
    for(auto v : g[u])
    {
        if(v == pre) continue;
        dfs1(v , u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u)
{
    pos[dfn[u] = ++num] = u;
    if(!son[u]) return;
    top[son[u]] = top[u];
    dfs2(son[u]);
    for(auto v : g[u])
    {
        if(v == fa[u] || v == son[u]) continue;
        top[v] = v;
        dfs2(v);
    }
    low[u] = num;
}

void pushup(int num) {sum[num] = sum[num << 1] + sum[num << 1 | 1];}

void build(int num , int l , int r)
{
    if(l == r) {sum[num] = 1; return;}
    int mid = l + r >> 1;
    build(num << 1 , l , mid); build(num << 1 | 1 , mid + 1 , r);
    pushup(num);
}

void update(int num , int l , int r , int x , int y)
{
    if(l > y || r < x) return;
    if(l >= x && r <= y) {tag[num] = 1 , sum[num] = 0; return;}
    int mid = l + r >> 1;
    update(num << 1 , l , mid , x , y);
    update(num << 1 | 1 , mid + 1 , r , x , y);
    pushup(num);
}

int query(int num , int l , int r , int x , int y)
{
    if(l > y || r < x) return 0;
    if(l >= x && r <= y) return sum[num];
    if(tag[num]) tag[num << 1] = tag[num << 1 | 1] = 1 , sum[num << 1] = sum[num << 1 | 1] = 0;
    int mid = l + r >> 1;
    return query(num << 1 , l , mid , x , y) + query(num << 1 | 1 , mid + 1 , r , x , y);
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1 , u , v ; i <= m ; i++) cin >> x[i] >> y[i];
    int t;
    while(1)
    {
        cin >> t;
        if(t == -1) break;
        int a , b; cin >> a >> b;
        o[++tot] = {t , a , b};
        if(!t) del[{a , b}] = del[{b , a}] = 1;
    }
    for(int i = 1 ; i <= n ; i++) fa[i] = i;
    for(int i = 1 ; i <= m ; i++)
    {
        int u = find(x[i]) , v = find(y[i]);
        if(!del[{x[i] , y[i]}] && fa[u] != v)
        {
            fa[u] = v;
            g[u].push_back(v);
            g[v].push_back(u);
            vis[i] = 1;
        }
    }
    memset(fa , 0 , sizeof fa);
    dfs1(1 , 0);
    dfs2(1);
    build(1 , 1 , n);
    for(int i = 1 ; i <= m ; i++)
    {
        if(vis[i] || del[{x[i] , y[i]}]) continue;
        int u = x[i] , v = y[i];
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]]) swap(u , v);
            update(1 , 1 , num , dfn[top[u]] , dfn[u]);
            u = fa[top[u]];
        }
        if(u != v)
        {
            if(dep[u] > dep[v]) swap(u , v);
            update(1 , 1 , num , dfn[u] + 1 , dfn[v]);
        }
    }
    queue <int> q;
    for(int i = tot ; i >= 1 ; i--)
    {
        int ans = 0 , t = o[i].op , u = o[i].a , v = o[i].b;
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]]) swap(u , v);
            if(t) ans += query(1 , 1 , tot , dfn[top[u]] , dfn[u]);
            else update(1 , 1 , tot , dfn[top[u]] , dfn[u]);
            u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u , v);
        if(t) q.push(ans + query(1 , 1 , tot , dfn[u] + 1 , dfn[v]));
        else update(1 , 1 , num , dfn[u] + 1 , dfn[v]);
    }
    while(!q.empty()) cout << q.front() << '\n' , q.pop();
    return 0;
}