【题解】10.31模拟赛T1：世界树的考验

solution

重要思想：边权转化为点权。定义点权为所有与之相连的边边权亦或和
把问题转化为把所有点权变为0的最小次数
证明可行：最终态所有点权为0。任何时刻必定存在度数为1的点并把它删掉，相当于删掉一条边，最终可以删光。
一次操作选择两个点，只会改变这两个点的权值，中途的点权并不会变。因为中途的点旁边连着两条边，亦或两遍不变
所以先把点权相同的点对删掉，然后剩下互不相同的点，通过状压跑一个记忆化dfs
状压状态$t$，若第$i$位是1，说明还存在点权为$i$的点
每次选择两个存在的点，相亦或

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
int n, dp[maxn], power[maxn], s[maxn], sum[maxn], ans, t;

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;
}

int dfs(int t){
	if (!t) return 0;
	if (dp[t] != -1) return dp[t];
	dp[t] = 1e9;
	for (int i = 0; i < 16; ++i) if (t & power[i])
	for (int j = 0; j < 16; ++j) if ((t & power[j]) && i != j){
		int p = i ^ j, nxt = t ^ power[i] ^ power[j] ^ power[p];
		if (t & power[p]) dp[t] = min(dp[t], dfs(nxt) + 2); else
		dp[t] = min(dp[t], dfs(nxt) + 1);
	}
	return dp[t];
}

int main(){
	freopen("trial.in", "r", stdin);
	freopen("trial.out", "w", stdout);
	n = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read(), z = read();
		s[x] ^= z, s[y] ^= z;
	}
	for (int i = 0; i < n; ++i) ++sum[s[i]];
	power[0] = 1;
	for (int i = 1; i <= 16; ++i) power[i] = power[i - 1] << 1;
	for (int i = 1; i < 16; ++i) ans += sum[i] >> 1, t += power[i] * (sum[i] & 1);
	memset(dp, 255, sizeof(dp));
	printf("%d\n", ans + dfs(t));
	return 0;
}