令 $v_i$ 表示与 $i$ 相连的所有边的 $w_i$ 异或和。直接转化为 $v_{1\sim n}$，每次选两个数异或上一个值，求全部归零的最小次数。$\operatorname{xor}v_i=0$。

实际上等价于将 $v_i$ 划分为最多的子集，使得每个子集的异或和为 $0$，这样每个子集都可以操作点数减一次。把相同的 $v_i$ 配对去掉，然后 $v$ 里现在只剩下至多 $31$ 个数。

考虑一个显然假的做法：遍历一遍 $v$，如果当前出现了一个异或和为 $0$ 的子集就直接把这个子集删掉，一直做下去。

你感受一下这玩意好像也没那么假，所以只要随机打乱 $v$ 跑一万遍取最优答案就可以过了。

因为维数非常小的情况下瞎找几个数就能出一个线性相关组，所以随到一个可以求出最优解的顺序应该是容易的。

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9,N=1e5+7,K=32,L=2e5+7;
const ll J=1e18;
int n,q,a[N],c[K],ans;
void mian() {
	scanf("%d",&n),ans=0;
	for (int i=0;i<K;i++) c[i]=0; for (int i=1;i<=n;i++) a[i]=0;
	for (int i=1,x,y,z;i<n;i++) scanf("%d%d%d",&x,&y,&z),a[x]^=z,a[y]^=z;
	for (int i=1;i<=n;i++) c[a[i]]++;
	c[0]=0; for (int i=1;i<K;i++) ans+=c[i]/2,c[i]%=2;
	vector<int> d;
	for (int i=1;i<K;i++) if (c[i]) d.pb(i);
	int mnn=I;
	for (int o=0;o<10000;o++) {
		shuffle(d.begin(),d.end(),mt19937(o+2));
		vector<int> v; int ret=0;
		for (int i:d) {
			bool flg=0;
			for (int s=0;s<1<<v.size();s++) {
				int sum=0;
				for (int j=0;j<v.size();j++) if (s>>j&1) sum^=v[j];
				if (sum==i) {
					vector<int> v1;
					for (int j=0;j<v.size();j++) if (s>>j&1^1) v1.pb(v[j]);
					flg=1,v=v1;
					break;
				}
			}
			if (!flg) v.pb(i),ret++;
		}
		mnn=min(mnn,ret);
	}
	cout<<ans+mnn<<"\n";
}
bool ORY; int main() {
	freopen("snow.in","r",stdin);
	freopen("snow.out","w",stdout);
	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}