C++(g++ 7.5.0) 解法, 执行用时: 93ms, 内存消耗: 15516K, 提交时间: 2023-07-25 15:39:29

#include <cstdio>
using namespace std;
#define max(a,b) (a>b ? a:b)
const int N=1e5+10;
int h[N],a[N],tr[N*31][2],tot=1,cnt,n;

struct edge {
	int h,v,w;
} e[N<<1];

inline void add(int u,int v,int w) {
	e[++cnt]=(edge) {
		h[u],v,w
	},h[u]=cnt;
}

void dfs(int x,int fa) {
	for (int i=h[x],v; i; i=e[i].h)
		if ((v=e[i].v)^fa) a[v]=a[x]^e[i].w,dfs(v,x);
}

void insert(int x) {
	int p=0;
	for (int i=30; ~i; i--) {
		int &j=tr[p][x>>i&1];
		if (!j) j=++tot;
		p=j;
	}
}

int search(int x) {
	int p=0,ret=0;
	for (int i=30,j; ~i; i--) {
		j=x>>i&1;
		if (tr[p][j^1]) ret=(ret<<1)+(j^1),p=tr[p][j^1];
		else ret=(ret<<1)+j,p=tr[p][j];
	}
	return ret^x;
}

int main() {
	scanf("%d",&n);
	for (int i=0,u,v,w; i<n-1; i++)
		scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	dfs(0,-1);
	for (int i=0; i<n; i++) insert(a[i]);
	int ans=0;
	for (int i=0; i<n; i++) ans=max(ans,search(a[i]));
	printf("%d",ans);
	return 0;
}
// https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44782843

C++14(g++5.4) 解法, 执行用时: 98ms, 内存消耗: 15480K, 提交时间: 2020-08-22 19:30:36

#include <cstdio>
using namespace std;
#define max(a,b) (a>b ? a:b)
const int N=1e5+10;
int h[N],a[N],tr[N*31][2],tot=1,cnt,n;

struct edge {
	int h,v,w;
} e[N<<1];

inline void add(int u,int v,int w) {
	e[++cnt]=(edge) {
		h[u],v,w
	},h[u]=cnt;
}

void dfs(int x,int fa) {
	for (int i=h[x],v; i; i=e[i].h)
		if ((v=e[i].v)^fa) a[v]=a[x]^e[i].w,dfs(v,x);
}

void insert(int x) {
	int p=0;
	for (int i=30; ~i; i--) {
		int &j=tr[p][x>>i&1];
		if (!j) j=++tot;
		p=j;
	}
}

int search(int x) {
	int p=0,ret=0;
	for (int i=30,j; ~i; i--) {
		j=x>>i&1;
		if (tr[p][j^1]) ret=(ret<<1)+(j^1),p=tr[p][j^1];
		else ret=(ret<<1)+j,p=tr[p][j];
	}
	return ret^x;
}

int main() {
	scanf("%d",&n);
	for (int i=0,u,v,w; i<n-1; i++)
		scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	dfs(0,-1);
	for (int i=0; i<n; i++) insert(a[i]);
	int ans=0;
	for (int i=0; i<n; i++) ans=max(ans,search(a[i]));
	printf("%d",ans);
	return 0;
}

C++ 解法, 执行用时: 134ms, 内存消耗: 12920K, 提交时间: 2021-12-24 22:00:58

#include<bits/stdc++.h>
using namespace std;
int te[3000001][2],tot,a[3000001],n,ans=INT_MIN;
void ru(int x){
    int p=0;
    for(int k=30;~k;k--){int &s=te[p][x>>k&1];if(!s)s=++tot;p=s;}
}
int chu(int x){   
    int ans=0,p=0;
    for(int i=30;~i;i--){int s=x>>i&1;if(te[p][!s])ans+=1<<i,p=te[p][!s];else p=te[p][s];}
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++)cin>>a[i]>>a[i]>>a[i],ru(a[i]);
    for(int i=1;i<n;i++)ans=max(ans,chu(a[i]));
    cout<<ans;
    return 0;
}