10pts玄学re求调教
查看原帖
10pts玄学re求调教
754502
_AyachiNene楼主2023/8/30 11:52

把这行删了就不会re

Xor[v]=Xor[u]^e[i].val;
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int nxt,to,val;
}e[114514*2];
int head[114514],cnt_edge;
void add(int u,int v,int w)
{
	e[++cnt_edge].val=w;
	e[cnt_edge].to=v;
	e[cnt_edge].nxt=head[u];
	head[u]=cnt_edge;
}
int n;
int Xor[114514];
int trie[1145141][3];
int cnt;
void insert(int x)
{
	int root=0;
	for(int i=31;i>=1;i--)
	{
		int sub=x&(1<<(i-1));
		if(!trie[root][sub])
			trie[root][sub]=++cnt;
		root=trie[root][sub];
	}
}
int query(int x)
{
	int ans=0,root=0;
	for(int i=31;i>=1;i--)
	{
		int sub=x&(1<<(i-1));
		if(trie[root][!sub])
			ans+=(1<<(i-1)),root=trie[root][!sub];
		else
			root=trie[root][sub];
	}
	return ans;
}
void dfs(int u,int fa)
{
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa)
			continue;
		Xor[v]=Xor[u]^e[i].val;
		insert(Xor[v]);
		dfs(v,u);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,query(Xor[i]));
	cout<<ans;
}
2023/8/30 11:52
加载中...