P4551 最长异或路径 题解

Link

P4551 最长异或路径

Solve

很奇怪为什么一道紫题这么水

因为异或的性质是异或同一个数两次等于啥都没干，所以(a)到(b)的路径异或值等于根节点异或到(a)的异或值异或根节点异或到(b)的异或值，所以先预处理出每个数到根节点的异或值(dis[i])。

对于每个(dis[i])我们找到另外一个(dis[j])使得(dis[i]^dis[j])最大，(01trie)就可以很好的做到这一点。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005,maxe=200005;
int N,son[maxe],nxt[maxe],lnk[maxn],w[maxe],dis[maxn],cnt,tot,ans;

struct trie{
	int ch[2];
}t[maxn*30];

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}

inline void add_e(int x,int y,int z){son[++cnt]=y;w[cnt]=z,nxt[cnt]=lnk[x];lnk[x]=cnt;}

void DFS(int x,int fa,int v){
	dis[x]=v;
	for(int j=lnk[x];j;j=nxt[j]){
		if(son[j]==fa)continue;
		DFS(son[j],x,v^w[j]);
	}
}

void build(int val,int x){
	for(int i=30;i>=0;i--){
		bool c=(val>>i)&1;
		if(!t[x].ch[c])t[x].ch[c]=++tot;
		x=t[x].ch[c];
	}
	return ;
}

int query(int val,int x){
	int ret=0;
	for(int i=30;i>=0;i--){
		bool c=(val>>i)&1;
		if(t[x].ch[c^1]){
			 ret+=1<<i;
			x=t[x].ch[c^1];
		}
		else x=t[x].ch[c];
	}
	return ret;
}

int main(){
	freopen("P4551.in","r",stdin);
	freopen("P4551.out","w",stdout);
	N=read();
	for(int i=1;i<N;i++){
		int x=read(),y=read(),z=read();
		add_e(x,y,z);add_e(y,x,z);
	}
	DFS(1,-1,0);
	for(int i=1;i<=N;i++)build(dis[i],0);
	for(int i=1;i<=N;i++)
	ans=max(ans,query(dis[i],0));
	printf("%d
",ans);
	return 0;
}