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