codeforcesRound#259(div2)E解题报告

解法：

首先我们可以明确一点，这就是一个图的遍历，找一个点，设为起点，建立一个搜索遍历树，对于树每一个点，我们完全可以控制奇偶性，假设：

目前访问的点为v，父节点为fa，如若点v不符合当前的奇偶性，则就让父节点到v绕一次，这样 odd[v] ^= 1, fa[v] ^= 1，这样我们可以完全保证完全控制子节点，将不符合要求的奇偶性调整成符合要求的奇偶性。同时父节点的奇偶性也在改变。

通过上述的操作，我们可以每次保证子节点的奇偶性符合要求，然而父节点的奇偶性如若不符合要求，则可以通过调整父节点 与 父节点的父节点来调整奇偶性，这样我们就可以奇偶性传递，最终传递到根节点。根节点如若不符合该如何调整呢？由于我们是走遍历树，到达叶节点还要回来的，意味着我们要走至少两次根节点，一次是出发，一次是最后一次回归。我们可以将根节点 r1 调整到根节点的其中一个子节点r2，使得奇偶性再次得到调整

代码：

#include 
#include 
#define N_max 123456

using namespace std;

int n, m, fa[N_max], want[N_max];
int Odd_n, Odd_x, haveOdd[N_max];
vector  G[N_max], ans;

int getf(int x) {
	return (fa[x] == x) ? x : fa[x] = getf(fa[x]);
}
void addedge(int x, int y) {
	G[x].push_back(y);
}

void init() {
	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {
	int x, y;

	scanf("%d%d", &x, &y);

	int tmpx=getf(x);
	int tmpy=getf(y);
	if (tmpx != tmpy) {
	fa[tmpx] = tmpy;
	addedge(x, y);
	addedge(y, x);
	}
	}

	for (int i = 1; i <= n; i++) {
	scanf("%d", &want[i]);

	if (want[i]) haveOdd[getf(i)] = 1;
	}

	for (int i = 1; i <= n; i++)
	if (haveOdd[i]) {
	Odd_n++;
	Odd_x = i;
	}
}

void dfs(int now, int pre) {
	ans.push_back(now);
	want[now] ^= 1;

	for (int i = 0; i < G[now].size(); i++) {
	int nex = G[now][i];
	if (nex == pre) continue;

	dfs(nex, now);
	ans.push_back(now);
	want[now] ^= 1;

	if (want[nex]) {
	ans.push_back(nex);
	want[nex] ^= 1;
	ans.push_back(now);
	want[now] ^= 1;
	}
	}
}

void solve() {
	if (Odd_n == 0) {
	printf("0\n");
	return;
	}

	if (Odd_n > 1) {
	printf("-1\n");
	return;
	}

	dfs(Odd_x, -1);
	int x = 0;
	if (want[Odd_x]) x=1;

	printf("%d\n", ans.size() - x);
	for (int i = x; i < ans.size(); i++)
	printf("%d ", ans[i]);
}

int main() {
	init();
	solve();
}