题意：
给定一张 \(n\) 个点 \(m\) 条边无向连通图，以及 \(q\) 个点对 \((a,b)\)，出事每条边权值为 \(0\)。对于每个点对我们需要找一条从一个点到另一个点的简单路径，将所有边的权值加一。要求构造一种方案使得每条边权值都是偶数。如果不行，输出最少还要几个点对才能满足要求。
\(n,m \le 10^5\)。
思路：
这个条件不难联想到欧拉回路，我们尝试构造一个图 \(G'\) 使得这 \(q\) 个点对是这张图的所有边。
如果这张图存在欧拉回路，则我们只用在回路最后一条边反向走一遍便能满足要求。回到原图，随便一棵生成树上走两点路径即可。
如果不存在欧拉回路，说明一定有奇点，这就会导致有的边边权是奇数。具体而言，我们记录每个点所有相邻边的边权和的奇偶性。显然一个点对只会改变两个端点，所以如果不存在欧拉回路，则必然不成立。需要再加上奇点个数除以二个。
然后就没了。
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e5 + 5;
int n, m, q;
vector<int> e[N], E[N];
int cnt[N] = {0};
int a[N] = {0}, b[N] = {0};
int p[N] = {0};
int fnd(int x) {
if (p[x] == x)
return x;
return p[x] = fnd(p[x]);
}
void unn(int x, int y) {
p[fnd(x)] = fnd(y);
}
int pr[N] = {0}, dth[N] = {0};
void srh(int x, int Pr, int d) {
dth[x] = d, pr[x] = Pr;
for (auto i: E[x])
if (i != Pr)
srh(i, x, d + 1);
}
int fnd_lca(int x, int y) {
if (x == y)
return x;
if (dth[x] < dth[y])
swap(x, y);
return fnd_lca(pr[x], y);
}
void fnd_prx(int x, int anc) {
if (x == anc)
return;
printf("%d ", x);
fnd_prx(pr[x], anc);
}
void fnd_suf(int x, int anc) {
if (x == anc)
return;
fnd_suf(pr[x], anc);
printf("%d ", x);
}
void fnd_pth(int x, int y) {
int lca = fnd_lca(x, y);
printf("%d\n", dth[x] + dth[y] - 2 * dth[lca] + 1);
fnd_prx(x, lca);
printf("%d ", lca);
fnd_suf(y, lca);
printf("\n");
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, u, v; i <= m; i++) {
scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &a[i], &b[i]);
cnt[a[i]]++, cnt[b[i]]++;
}
int odd = 0;
for (int i = 1; i <= n; i++)
odd += cnt[i] % 2;
if (odd > 0) {
printf("No\n%d\n", odd / 2);
return 0;
}
for (int i = 1; i <= n; i++)
p[i] = i;
for (int i = 1; i <= n; i++)
for (auto j: e[i])
if (fnd(i) != fnd(j)) {
unn(i, j);
E[i].push_back(j);
E[j].push_back(i);
}
srh(1, 1, 1);
printf("YES\n");
for (int i = 1; i <= q; i++)
fnd_pth(a[i], b[i]);
return 0;
}