C++11(clang++ 3.9) 解法, 执行用时: 314ms, 内存消耗: 13816K, 提交时间: 2020-08-05 15:17:22

#include<bits/stdc++.h>

using namespace std;
const int MAX_N = 202020;

int fd(int N, int* A, int M, int* B, int K)
{
	if(N==0||M==0)
		return 1<<K;
	if(K==0)
		return 0;
	int X=std::lower_bound(A, A+N, ((A[0]>>K-1)|1)<<K-1)-A;
	int Y=std::lower_bound(B, B+M, ((B[0]>>K-1)|1)<<K-1)-B;
	if(X==0 && Y==M || X==N && Y==0)
		return fd(N, A, M, B, K-1) + (1<<(K-1));
	return std::min(fd(X, A, Y, B, K-1), fd(N-X, A+X, M-Y, B+Y, K-1));
}
long long solve(int N, int* A, int K)
{
	if(N == 1)
		return 0;
	int X = lower_bound(A, A+N, ((A[0] >> (K-1))|1) << (K-1)) - A;
	if(X==0 || X==N)
		return solve(N, A, K-1);
	return (1ll << (K-1)) + fd(X, A, N-X, A+X, K-1) + solve(X, A, K-1)+solve(N-X, A+X, K-1);
}

struct Edge{
	int to, va;
};

vector<Edge> G[MAX_N];

int N, A[MAX_N];

bool vis[MAX_N];

void dfs(int x)
{
	vis[x] = 1;
	for(Edge e: G[x])
	if(!vis[e.to])
	{
		A[e.to] = A[x] ^ e.va;
		dfs(e.to);
	}
}

int main()
{
	scanf("%d", &N);
	for(int i = 1; i < N; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u].push_back({v, w});
		G[v].push_back({u, w});
	}
	A[0] = 0;
	
	
	dfs(0);
	std::sort(A, A+N);
	N = std::unique(A, A+N) - A;
	printf("%lld\n", solve(N, A, 30));
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 254ms, 内存消耗: 37464K, 提交时间: 2020-07-25 14:27:28

#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=1e5+10;
const ll inf=1e18;
int s[N],a[2][N*30],h[N*30],l[N*30],r[N*30];vector<pii>e[N];
void dfs(int x){
	for(auto&i:e[x])if(s[i.fr]==-1){
		s[i.fr]=s[x]^i.sc;dfs(i.fr);
	}
}
int main(){int n;
	scanf("%d",&n);
	rep(i,0,n-1)s[i]=-1;
	rep(i,2,n){int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back({y,z});
		e[y].push_back({x,z});
	}
	s[0]=0;dfs(0);int tot=1;h[1]=30;
	sort(s,s+n);
	rep(i,0,n-1){int x=1;
		dep(j,29,0){
			int t=(s[i]>>j)&1;
			if(!a[t][x]){
				a[t][x]=++tot;
				h[tot]=h[x]-1;l[tot]=r[tot]=i;
			}
			x=a[t][x];r[x]=i;
		}
	}ll ans=0;
	rep(i,1,tot)if(a[0][i]&&a[1][i]){
		int x=a[0][i],y=a[1][i];
		if(r[x]-l[x]<r[y]-l[y])swap(x,y);
		int res=1<<30;
		rep(j,l[y],r[y]){int nw=x;
			dep(k,h[x]-1,0){
				int t=(s[j]>>k)&1;
				if(!a[t][nw])t^=1;
				nw=a[t][nw];
			}
			res=min(res,s[j]^s[l[nw]]);
		}
		ans+=res;
	}
	printf("%lld\n",ans);
}