CF453C：Little Pony and Summer Sun Celebration

原题传送门
题意： 给出一张N个点M条边的无向图，有些点要求经过奇数次，有点要求经过偶数次，要求寻找一条满足要求的路径，且该路径长度不超过点数的四倍。
$N,M\le 100000$
首先特判，若所有点都需经过偶数次，则答案为0
否则任选一个需经过奇数次的点为根建树。很明显，叶子结点只访问一次，非叶节点只访问两次
但是，如果非叶结点要求访问奇数次，上面的做法就会出现问题。这时只要让它的父亲多遍历这个点一次即可。
此时根节点可能会出问题，他可能遍历了一遍自己的父亲（并不存在），所以要将输出序列长度减去3，是的0节点不被遍历

Code：

#include <bits/stdc++.h>
#define maxn 400010
using namespace std;
struct Edge{
	int to, next;
}edge[maxn << 1];
int num, head[maxn], cnt, print[maxn], a[maxn], vis[maxn];
int n, m, rt;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y){ edge[++num] = (Edge) { y, head[x] }; head[x] = num; }

void dfs(int u, int pre){
	print[++cnt] = u, a[u] ^= 1, vis[u] = 1;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (!vis[v]) dfs(v, u), print[++cnt] = u, a[u] ^= 1;
	}
	if (a[u]) a[u] ^= 1, a[pre] ^= 1, print[++cnt] = pre, print[++cnt] = u;
}

int main(){
	n = read(), m = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read();
		addedge(x, y); addedge(y, x);
	}
	for (int i = 1; i <= n; ++i){
		a[i] = read();
		if (a[i]) rt = i;
	}
	if (!rt) return puts("0"), 0;
	dfs(rt, 0);
	for (int i = 1; i <= n; ++i)
		if (a[i] && !vis[i]) return puts("-1"), 0;
	if (cnt > 1 && !print[cnt - 1]) cnt -= 3;
	printf("%d\n", cnt);
	for (int i = 1; i <= cnt; ++i) printf("%d ", print[i]);
	return 0;
}