AT3913 XOR Tree（巧妙转换+状压dp）

Step1:首先定义一个点的权值为与其相连边的异或和。那么修改一条路径，权值改变的只有两个端点。边权都为0和点权都为0实质相同。

Step2:那么现在和树的结构就没有什么关系了。每次选两个点，然后同时异或上一个值。求最小次数。

Step3:首先权值为0的不用修改了，贪心先把权值一样的两两分组。那么就会剩下至多15个数。因为只有15个数，考虑状压。如果几个数异或值为0，那么显然存在方案n-1次全部消完。那么就可以子集转移。

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

template<class T> inline void read(T &x) {

	x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();

	x = f ? -x : x;

	return ;

}

template<class T> inline void write(T x) {

	if (!x) {putchar(48);return ;}

	if (x < 0) x = -x, putchar('-');

	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;

	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;

}

const int N = 1e5 + 10, Limit = 1 << 15;

int val[N], cnt[15], res[Limit], f[Limit];

int main() {

	int n;

	read(n);

	for (int i = 1; i < n; i++) {

		int x, y, z; read(x), read(y), read(z);

		x++; y++; val[x] ^= z; val[y] ^= z;

	}

	for (int i = 1; i <= n; i++) cnt[val[i]]++;

	int ans = 0, S = 0;

	for (int i = 1; i <= 15; i++)

		ans += cnt[i] / 2, S |= (cnt[i] & 1) << (i - 1);

	for (int i = 1, cnt; i < Limit; i++) {

		cnt = 0;

		for (int j = 1; j <= 15; j++)

			if ((i >> (j - 1)) & 1) res[i] ^= j, cnt++;

		f[i] = cnt - 1;

	}

	for (int i = 1; i < Limit; i++)

		if (!res[i])

			for (int j = i; j; j = (j - 1) & i)

				if (!res[j]) f[i] = min(f[i], f[j] + f[i ^ j]);

	printf("%d\n", ans + f[S]);

	return 0;

}