题解

每次询问都可以重新分组，所以之前具体把哪两条道路放在一起，并不需要保留。我们要知道的是，当前图最多能组成多少对相邻边。

不同连通块的边没有公共端点，肯定不能配在一起。可以先研究一个含 $e$ 条边的连通块。

每组用掉两条边，答案至多是 $\lfloor e/2\rfloor$。如果这个上界总能达到，图的具体形状就不再影响答案，只需维护连通块的边数。

一个连通块真的只会剩下至多一条边

我们给边指定一个负责处理它的端点。在同一个点负责的边里，两两配对一定合法，因为它们共享这个点；每条边又只交给一个点处理，不会被重复使用。

为了描述方便，把边指向负责它的那个端点。现在要让除某一个点之外的点，入度都为偶数。这样只有最后那个点可能剩下一条边。

任选一棵生成树和一个根。非树边先随意定向，然后沿生成树从叶子往上处理。

处理非根点 $u$ 时，它与孩子之间的树边都已经定向，非树边也已经定向，只有与父亲之间的边没定。

• 当前入度是奇数，就把父边指向 $u$，补成偶数。
• 当前入度是偶数，就把父边指向父亲，不再增加 $u$ 的入度。

处理完 $u$ 后，它的入度为偶数，之后也不会再改变。这样一路处理到根，除根以外的点都能把自己收到的边两两配完。

所有点的入度之和等于 $e$。其他点的入度都是偶数，根的入度就与 $e$ 同奇偶。因此 $e$ 为偶数时全部配完，$e$ 为奇数时恰好剩下一条，达到 $\lfloor e/2\rfloor$。

这段构造只用来证明，不需要真的在程序里执行。

加一条边，只会影响一个或两个连通块

当前已经加入 $k$ 条边，各个连通块的边数为 $e_C$，答案为

$$\sum_C\left\lfloor\frac{e_C}{2}\right\rfloor.$$

如果某个连通块有奇数条边，它会剩下一条；偶数边的块不会剩。设奇数边连通块有 $c$ 个，总共就有 $c$ 条边无法参与配对，所以也可以写成

$$\frac{k-c}{2}.$$

用并查集维护连通块，并在每个根上存边数的奇偶性 $p$。加入边 $(u,v)$ 时分两种情况。

如果两端已经在同一块里，这个块的边数增加一，奇偶性翻转。先从 $c$ 中减掉旧的 $p$，翻转后再加上新的 $p$。

如果两端属于不同块，先减掉两块原来的奇偶贡献，再合并。新块的边数是 $e_1+e_2+1$，所以新奇偶性为

$$p_1\mathbin{\mathrm{xor}}p_2\mathbin{\mathrm{xor}}1.$$

最后把新块的奇偶贡献加回 $c$。式子里的 $1$ 是刚加入的这条边，不能漏掉。每次维护完成，输出 $(k-c)/2$。

空图的每个点都是零条边的连通块，初始 $c=0$。上面两种更新分别与实际的内部加边、合并加边一致，因此维护到任何时刻，$c$ 都是当前奇数边连通块的数量。

并查集采用路径压缩和按大小合并，总时间 $O(n+q\alpha(n))$，空间 $O(n)$，无需保存邻接表。

部分分与这个结论的关系

只有至多 $16$ 条边的 12 分，不必先得到连通块结论。用状态压缩枚举边的配对，令 $f(S)$ 表示集合 $S$ 中的边最多能配多少组。取其中一条边 $i$，要么舍弃它，要么与一条共享端点的边 $j$ 配成一组，转移到删掉这两条边的集合。

每个最优方案里，$i$ 必然属于这两种情况之一，所以转移完整。时间 $O(q2^q)$，空间 $O(2^q+q)$；同一张表可以回答所有加边前缀，不必为每次询问重算。

$n,q\le2000$ 的 18 分，可以在每次加边后重新遍历连通块，统计度数和除以二得到边数，再加上 $\lfloor e/2\rfloor$。总时间 $O(q(n+q))$、空间 $O(n+q)$。它也能处理第一档，所以两档共 30 分。

森林的 20 分可以先只证明树的结论。树中没有非树边，仍能用上面的从叶到根定向法把边配好；而一个含 $s$ 个点的树有 $s-1$ 条边，贡献就是 $\lfloor(s-1)/2\rfloor$。并查集只维护点数即可，每次加边一定合并两个不同块，不会遇到内部加边。复杂度与完整做法同阶。

规模较小的重算与森林性质结合，可以保证前面三档的 50 分。推广到一般图时，需要补上两个地方，证明含环的连通块仍能配好，以及处理同一个连通块内部继续加边。

参考代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> fa(n + 1), sz(n + 1, 1), parity(n + 1);
    iota(fa.begin(), fa.end(), 0);
    auto find = [&](int x) {
        while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }
        return x;
    };
    int odd = 0;
    for (int i = 1; i <= q; ++i) {
        int u, v;
        cin >> u >> v;
        u = find(u), v = find(v);
        if (u == v) {
            odd -= parity[u];
            parity[u] ^= 1;
            odd += parity[u];
        } else {
            odd -= parity[u] + parity[v];
            if (sz[u] < sz[v]) swap(u, v);
            fa[v] = u;
            sz[u] += sz[v];
            parity[u] ^= parity[v] ^ 1;
            odd += parity[u];
        }
        cout << (i - odd) / 2 << '\n';
    }
}