求一个计数方案奇偶性的题考虑套路的交换两个元素。考虑最开始选的两条边，如果它们没有交，那么互换顺序之后结果不变。我们只需要统计相交的情况即可。
再考虑边相邻的情况。对于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;
}