[AGC050F] NAND Tree

求一个计数方案奇偶性的题考虑套路的交换两个元素。考虑最开始选的两条边，如果它们没有交，那么互换顺序之后结果不变。我们只需要统计相交的情况即可。

再考虑边相邻的情况。对于y---x---z，按两种顺序缩边的结果分别为 \(\operatorname{NAND}(\operatorname{NAND}(y,x),z)\) 和 \(\operatorname{NAND}(y,\operatorname{NAND}(x,z))\)。注意到 \(y=z\) 时两者等价。而 \(y\neq z\) 时，我们会得到不同的结果。

于是有了关键性质：我们将规则修改为每次选择一个点，如下图缩边：

  \       |      /                       \ | /
--- x --- y --- z ---        =>        --- x ---
  /       |      \                       / | \

答案不会变化。

先考虑共有偶数条边的情况。我们称一个节点是好的当且仅当它的权值为 1 且有奇数种方案使得它最后被保留下来。答案即为好点的数量。

考虑检查一个节点 \(x\) 是否是好的。我们先将 \(x\) 设为根，并假设每次操作都涉及根（不然两个方向等价）。

共有奇数条边的情况，枚举第一次操作转化为偶数条边即可。

按官方题解的说法这个东西相当于拓扑序计数（？），直接写一个就WA了。实际上考虑将树选完肯定会是一组完美匹配，我们这里把一组匹配到的点缩到一起，答案相当于这棵新树的拓扑序计数。

#include <bits/stdc++.h>

using namespace std;

#define ctz(x) (!(x)?0:__builtin_ctz((x)))

const int N = 505;

inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
	return s * f;
}

set<int> e[N], t[N];

int id[N], val[N], a[N], n;

inline void shrink(int u, int v) {
	if (u > v) swap(u, v);
	for (int i = 1; i < v; ++i) id[i] = i; id[v] = u;
	for (int i = v + 1; i <= n; ++i) id[i] = i - 1;
	for (int i = 1; i <= n; ++i) val[id[i]] = a[i], t[i].clear();
	val[id[u]] = !(a[u] & a[v]);
	for (int i = 1; i <= n; ++i) {
		for (int j : e[i])
			if (id[i] != id[j])
				t[id[i]].insert(id[j]);
	}
}

int siz[N];
bool par[N];

inline int dfs(int now, int fa) {
	siz[now] = 1;
	for (int i : t[now])
		if (i != fa) {
			int v = dfs(i, now);
			if (v == -1) return -1;
			if (v) {
				if (!par[now]) par[now] = 1;
				else return -1;
			}
			siz[now] += siz[i];
		}
	return par[now] ^ 1;
}

inline int calc(int n) {
	int res = 0, fn = 0;
	for (int i = 1; i <= n / 2; ++i) fn += ctz(i);
	for (int i = 1; i <= n; ++i) {
		if (!val[i]) continue;
		for (int j = 1; j <= n; ++j) par[j] = 0;
		if (dfs(i, 0) == -1) continue;
		int cnt = fn;
		for (int j = 1; j <= n; ++j)
			if (par[j]) cnt -= ctz(siz[j] / 2);//, cerr << "C : " << ctz(siz[j] / 2) << endl;;
		res ^= (cnt == 0);
//		cerr << fn << ' ' << cnt << ' ' << res << endl;
	} return res;
}

int main() {
	n = read();
	for (int i = 1, u, v; i < n; ++i) {
		u = read(); v = read();
		e[u].insert(v);
		e[v].insert(u);
	}
	for (int i = 1; i <= n; ++i) a[i] = read();
	if (n & 1) {
		for (int i = 1; i <= n; ++i)
			t[i] = e[i], val[i] = a[i];
		printf("%d\n", calc(n));
	} else {
		int res = 0;
		for (int i = 1; i <= n; ++i)
			for (int j : e[i])
				if (i < j) {
					shrink(i, j);
					res ^= calc(n - 1);
				}
		printf("%d\n", res);
	}
	return 0;
}