[Medium] CF2025F Choose Your Queries

简要题意

有 $n$ 个数 $a_1,\cdots,a_n$，初始时全为 $0$。

有 $m$ 次操作，每次操作给出 $x,y$，你需要选择 $a_x,a_y$ 中的任意一个，令其加上或减去 $1$，你需要保证任何一个数在任意时刻都是非负整数。

你需要使得最后得到的 $n$ 个数的总和最小，输出任意一组合法的方案。

$1\leq n,m\leq 3\times 10^5$。

思路

感觉可能比较平凡？连我这样的构造菜鸡都可以做出来。

首先二元关系直接建图，并且将偏向关系（在本题中，就是对哪一个端点进行操作）体现为边的方向。具体地，我们可以建出一张图，边 $(x,y)$ 表示有操作 $(x,y)$。我们需要对其定向，假如存在边 $x\to y$ 表示对 $x$ 进行操作。

但是这样我们忽略了加上还是减去 $1$ 这个限制，不过稍作分析发现我们其实不需要。假如已经定向了，那么一个显然且正确的分配 $\pm 1$ 的方法是：遍历每个点的出边（按照操作时间排序），奇数次遇到的分配 $+1$，偶数次遇到的分配 $-1$，这样对于出度为奇数的点，答案的贡献是 $1$，否则是 $0$。

现在的问题是如何为我们建出的无向图每条边定向，使得奇数点最少，由于每一个连通块问题是独立的，不妨对于每一个连通块分别考虑。

不妨贪心，尽可能让每个点度数为偶数，然后你发现不会做，开始枚举可能的做法，然后你枚举到了 dfs 树。

对图跑出 dfs 树，然后递归，对于点 $u$，假设儿子节点全部调整为出度为偶数了，那么只需要考虑 $u$ 的返祖边以及与父亲直接相连的一条边，由于只需要保证奇偶性，因此只需要留住一条边，其他边随意定向，用留下的边就可以实现这个点出度为偶数，为了方便，将这条留下的边设定为与父亲直接相连的一条边即可。

这样，只要存在与父亲直接相连的边，一定可以调整到度数为偶数，故只有根节点可能无法调整，一个连通块最多贡献 $1$ 的答案。

现在我们需要证明这个做法是正确的，由于可行性显然成立，故只需要证明用我们的做法，根节点调整后为奇数时，答案同样也为 $1$。考虑反证法，若答案为 $0$，则我们需要在原本方案下，反转奇数条边，那么这同样会改变其子节点的出度，我们接下来有两种决策：

• 结束决策，反转奇数条边，一定会影响除去根节点外，一个点的入度奇偶性，答案至少为 $1$。
• 向下继续调整，由于那么在子树上回到了我们最初的问题，不能结束决策，只能继续调整，调整到叶子节点后，由于缺乏子树，无法调整，至少会产生 $1$ 的贡献。

于是证明了我们的结论，如此调整，时间复杂度 $O(n+m)$，按照实现不同，可能会带 $\log$。

代码

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

const int N = 3e5 + 5;
int n, m, deg[N], dep[N];
vector<pair<int,int>> g[N], g2[N];
pair<int,int> a[N];

void dfs(int u, int fa){
    dep[u] = dep[fa] + 1;
    for(auto [v, id] : g[u]){
        if(dep[v]) continue;
        dfs(v, u);
    }
    int par = 0;
    for(auto [v, id] : g[u]){
        if(dep[v] > dep[u]) continue;
        if(v == fa && !par){ par = id; continue; }
        g2[u].emplace_back(v, id);
        deg[u]++;
    }
    if(!par) return;
    if(deg[u] & 1) g2[u].emplace_back(fa, par), deg[u]++;
    else g2[fa].emplace_back(u, par), deg[fa]++;
}

string ans[N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int& u = a[i].first, &v = a[i].second;
        cin >> u >> v;
        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);
    }
    for(int i=1;i<=n;i++){
        if(!dep[i]) dfs(i, 0);
    }
    for(int i=1;i<=n;i++){
        int cnt = 0;
        sort(g2[i].begin(), g2[i].end(), [](auto x, auto y){
            return x.second < y.second;
        });
        for(auto [j, id] : g2[i]){
            cnt++;
            ans[id] = a[id].first == i ? "x" : "y";
            ans[id] += cnt & 1 ? "+" : "-";
        }
    }
    for(int i=1;i<=m;i++) cout << ans[i] << '\n';
    return 0;
}

// Written by xiezheyuan