题解：CF1044F DFS

· · 题解

考虑两个点之间连一条边会使得哪些点不行。手玩一下发现条件其实特别强。设新加进来的边为 (u, v)。不妨设 dep_u < dep_v。

发现每次行或者不行的点都可以通过几棵子树容斥得到，考虑将树拉到 dfn 序上处理，每次给不合法的点 +1，统计全局最小值的点并要求这个最小值是 0 的时候才有贡献。对于删边？把上述的权值反过来即可。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n, q;
const int N = 2e5 + 10;
vector <int> G[N];
int in[N], out[N], cnt;
int f[N][25], dep[N];
void dfs(int now, int fa) {
    in[now] = ++ cnt;
    dep[now] = dep[fa] + 1;
    f[now][0] = fa;
    for (int i = 1; i < 25; i ++) f[now][i] = f[f[now][i - 1]][i - 1];
    for (auto u : G[now]) {
        if(u == fa) continue ;
        dfs(u, now);
    }
    out[now] = cnt;
}
bool In(int u, int v) {
    return (in[u] <= in[v] && out[u] >= out[v]);
}
struct seg {
    #define ls (u << 1)
    #define rs (u << 1 | 1)
    int tr[N << 2], len[N << 2], minn[N << 2];
    int tag[N << 2];
    void pushup(int u) {
        minn[u] = min(minn[ls], minn[rs]);
        tr[u] = 0;
        if(minn[u] == minn[ls]) {
            tr[u] += tr[ls];
        }
        if(minn[u] == minn[rs]) {
            tr[u] += tr[rs];
        }
    }
    void upd(int u, int v) {
        tag[u] += v;
        minn[u] += v;
    }
    void pushdown(int u) {
        if(tag[u]) {
            upd(ls, tag[u]);
            upd(rs, tag[u]);
            tag[u] = 0;
        }
    } 
    void build(int u, int l, int r) {
        tr[u] = tag[u] = minn[u] = 0;
        // len[u] = r - l + 1;
        if(l == r) {
            tr[u] = 1;
            return ;
        }
        int mid = l + r >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(u);
    }
    void modify(int u, int l, int r, int L, int R, int v) {
        if(L <= l && r <= R) return upd(u, v), void();
        int mid = l + r >> 1;
        pushdown(u);
        if(L <= mid) modify(ls, l, mid, L, R, v);
        if(mid < R) modify(rs, mid + 1, r, L, R, v);
        pushup(u);
    }
    #undef ls
    #undef rs
} t;
typedef pair <int, int> pii;
map <pii, int> mp;
signed main(void) {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; i ++) {
        int u, v;
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 0);
    t.build(1, 1, n);
    while (q --) {
        int u, v;
        cin >> u >> v;
        int ver;
        if(!mp.count({min(u, v), max(u, v)})) {
            ver = 1;
            mp[{min(u, v), max(u, v)}] = 1;
        }
        else {
            ver = -1;
            mp.erase({min(u, v), max(u, v)});
        }
        if(dep[u] > dep[v]) swap(u, v);
        if(In(u, v)) {
            int to = v;
            for (int i = 24; i >= 0; i --) {
                if(dep[f[to][i]] > dep[u]) to = f[to][i];
            }
            t.modify(1, 1, n, in[to], out[to], ver);
            t.modify(1, 1, n, in[v], out[v], -ver);
        }
        else {
            t.modify(1, 1, n, 1, n, ver);
            t.modify(1, 1, n, in[u], out[u], -ver);
            t.modify(1, 1, n, in[v], out[v], -ver);
        }
        if(t.minn[1] == 0) cout << t.tr[1] << endl;
        else cout << 0 << endl;
        // cout << t.minn[4] << endl;
    }
    return 0;
}

::::