GroupBlog

1954: Pku3764 The xor-longest Path

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 897 Solved: 406
[ Submit][ Status][ Discuss]

Description

给定一棵n个点的带权树，求树上最长的异或和路径

Input

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.

Output

For each test case output the xor-length of the xor-longest path.

Sample Input

4
1 2 3
2 3 4
2 4 6

Sample Output

HINT

The xor-longest path is 1->2->3, which has length 7 (=3 ⊕ 4)
注意：结点下标从1开始到N....

Source

鸣谢陶文博

hzwer:

求出根到每个结点的边权异或和

问题转换为任选两点，异或和最大

在trie上从插入所有权值，再查询每个权值从高位到低位）

查询x的时候，每一位尽量走与x该位不同的结点

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int bin[35];
int n,ans,cnt;
int val[100005],last[100005];
struct edge{
	int to,next,v;
}e[200005];



//01字典树
struct trie{
	int cnt;
	int ch[3000005][2];//zis = 30 * MAXN
	void insert(int x)
	{
		int now=0;
		for(int i=30;i>=0;i--)
		{
			int t=x&bin[i];t>>=i;
			if(!ch[now][t])  ch[now][t]=++cnt;
			now=ch[now][t];
		}
	}

	void query(int x)
	{
		int tmp=0,now=0;//当前为x 寻找另一个y 使得x^y最大
		for(int i=30;i>=0;i--)
		{
			int t=x&bin[i];t>>=i;
			if(ch[now][t^1])now=ch[now][t^1],tmp+=bin[i];
			else now=ch[now][t];
		}
		ans=max(tmp,ans);
	}
}trie;







void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}


void dfs(int x,int fa)
{
	for(int i=last[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			val[e[i].to]=val[x]^e[i].v;
			dfs(e[i].to,x);
		}
}



int main()
{
	bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;

	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read(),w=read();
		insert(u,v,w);
	}
	dfs(1,0);

	for(int i=1;i<=n;i++)
		trie.insert(val[i]);
	for(int i=1;i<=n;i++)
		trie.query(val[i]);
	printf("%d",ans);
	return 0;
}