C++14(g++5.4) 解法, 执行用时: 347ms, 内存消耗: 13840K, 提交时间: 2019-12-10 00:57:28

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 31e5;

struct Node {
  int ch[2];
};
Node nodes[MAXN];
int sz;
int getXorMax(string s) {
  int ans = 0;
  int b = 1<<30;
  int cur = 0;
  for (auto ch: s) {
    int id = ch - '0';
    if (nodes[cur].ch[1-id]) ans |= b, cur = nodes[cur].ch[1-id];
    else if (nodes[cur].ch[id]) cur = nodes[cur].ch[id];
    else break;
    b >>=1;
  }
  return ans;
}
void insert(string s) {
  int cur = 0;
  for (auto ch: s) {
    int id = ch - '0';
    int &nxt = nodes[cur].ch[id];
    if (nxt == 0) nxt = ++sz;
    cur = nxt;
  }
}

vector<pair<int, int>> G[128*1024];
int n;
int best = 0;

void dfs(int s, int v, int f) {
  string vs = bitset<31>(v).to_string();
  best = max(best, getXorMax(vs));
  insert(vs);
  for (auto t: G[s]) if (t.first != f) {
    dfs(t.first, v^t.second, s);
  }
}

int main() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v, w; cin >> u >> v >> w;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
  }
  dfs(1, 0, 0);
  cout << best << endl;


}

C++(clang++11) 解法, 执行用时: 101ms, 内存消耗: 18592K, 提交时间: 2021-05-16 13:35:17

#include<bits/stdc++.h>
using namespace std;

vector<int>R[100005],W[100005];
int tot=0,trie[3200005][2],a[100005];
void insert(int x)
{
	int i,rt=0,op;
	for(i=30;i>=0;i--)
	{
		op=(x>>i)&1;
		if(!trie[rt][op])trie[rt][op]=++tot;
		rt=trie[rt][op];
	}
}
int search(int x)
{
	int i,rt=0,op,ans=0;
	for(i=30;i>=0;i--)
	{
		op=(x>>i)&1;
		if(trie[rt][op^1])rt=trie[rt][op^1],ans|=(1<<i);
		else rt=trie[rt][op];
	}
	return ans;
}
void DFS(int x,int fa,int s)
{
	int i,j;
	a[x]=s;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(j!=fa)DFS(j,x,s^W[x][i]);
	}
}
int main()
{
	int i,n,u,v,w,ans=0;
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		R[u].push_back(v),R[v].push_back(u);
		W[u].push_back(w),W[v].push_back(w); 
	}
	DFS(1,0,0);
	for(i=1;i<=n;i++)insert(a[i]),ans=max(ans,search(a[i]));
	printf("%d\n",ans);
	return 0;
}