奇偶树

题面

有一棵 $n$ 个节点的树，节点编号为 $1\sim n$ 。树的边权的取值只有 $0$ 和 $1$ ，且应当满足 $Q$ 个条件。每个条件形如 $(u,v,x)$ ，其中 $u$ 和 $v$ 是树中节点的编号， $x$ 是 $0$ 或 $1$ 。

条件的含义为树上从 $u$ 到 $v$ 的路径上的边权和在模 $2$ 意义下应与 $x$ 相等（即若 $x=0$ 则和应为偶数;若 $x=1$ 则和应为奇数）。

满足这 $Q$ 个条件的前提下，整棵树的边权有多少种方案。由于答案可能很大，请将方案数对 取模后输出。

题解

注意模 2 下的加法为异或。对于每个点，设 $d_x$ 表示从根节点到它的异或和，则一个条件 $(u,v,x)$ 即为 $d_u\oplus d_v=x$ ，其中 $\oplus$ 表示异或。那么用带权并查集维护即可。

代码

const int N = 1e5 + 5, mod = 1e9 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int fa[N], d[N];
	int find (int k) {
		if (fa[k] == k) return k;
		int t = fa[k];
		fa[k] = find(fa[k]);
		d[k] ^= d[t];
		return fa[k];
	}
	int qpow (int a, int b) {
		int ans = 1;
		for (; b; b >>= 1, a = 1ll * a * a % mod)
			if (b & 1) ans = 1ll * ans * a % mod;
		return ans;
	}
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i < n; i++) int u = Read(), v = Read();
		for (int i = 1; i <= n; i++) fa[i] = i;
		for (int i = 1; i <= m; i++) {
			int u = Read(), v = Read(), w = Read();
			int ru = find(u), rv = find(v);
			if (ru == rv && d[u] != (d[v] ^ w)) {
				puts("0"); return 0;
			} else if (ru != rv) {
				fa[ru] = rv;
				d[ru] = d[u] ^ d[v] ^ w;
			}
		}
		int cnt = 0;
		for (int i = 1; i <= n; i++) if (find(i) == i) cnt++;
		printf ("%d\n", qpow (2, cnt - 1));
		return 0;
	}
}

int main () {
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	Main::main();
	return 0;
}