POJ 3764 The xor-longest Path Trie树字典树

The xor-longest Path Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 7068 Accepted: 1515

Description

In an edge-weighted tree, the xor-length of a path p is defined as the xor sum of the weights of edges on p:

⊕ is the xor operator.

We say a path the xor-longest path if it has the largest xor-length. Given an edge-weighted tree with n nodes, can you find the xor-longest path? 　

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 0 1 3 1 2 4 1 3 6

Sample Output

7

Hint

The xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)

给定一棵树，边上有边权，求树上所有路径当中路径上的值异或最大的。

首先要知道异或的性质：x xor x=0

这个性质有什么用呢？假设0号点为根，我们算出所有点到它的路径的异或和之后，设为a[i]，则 i 到 j 的路径的异或和就为a[i]^a[j]，因为 i 和 j 在它们的LCA之前的路径上的所有值各被异或了两次，而同样的数字异或为0。

这样，我们求出所有点到根的路径异或和之后，把这些和变为二进制的0-1串，建立字典树。之后，穷举路径的起点，在字典树上寻找能够使异或和最大的路径终点。也就是对于每个固定的a[i]，寻找使异或和最大的a[j]。根据异或的性质，只要从高位开始依次选择与当前的a[i]某位上尽量相反的数即可。

复杂度O(nlogw)

#include <cstdio> #include <iostream> #include <string.h> #include <string> #include <map> #include <queue> #include <vector> #include <set> #include <algorithm> #include <math.h> #include <cmath> #include <stack> #define mem0(a) memset(a,0,sizeof(a)) #define meminf(a) memset(a,0x3f,sizeof(a)) using namespace std; typedef long long ll; typedef long double ld; const int maxn=100005,inf=0x3f3f3f3f; const ll llinf=0x3f3f3f3f3f3f3f3f; const ld pi=acos(-1.0L); int num; int head[maxn]; ll a[maxn]; bool visit[maxn]; struct Edge { int from,to,pre; ll dist; }; Edge edge[maxn*2]; void addedge(int from,int to,ll dist) { edge[num]=(Edge){from,to,head[from],dist}; head[from]=num++; edge[num]=(Edge){to,from,head[to],dist}; head[to]=num++; } void dfs(int now,ll val) { visit[now]=1; a[now]=val; for (int i=head[now];i!=-1;i=edge[i].pre) { int to=edge[i].to; if (!visit[to]) dfs(to,val^edge[i].dist); } } struct Tree{ int l,r; }; Tree tree[maxn*32]; void insert(int now,ll val,int depth) { if (depth==32) return; if ((val>>(31-depth))%2==1) { if (tree[now].l==-1) { tree[now].l=++num; tree[num].l=tree[num].r=-1; } insert(tree[now].l,val,depth+1); } else { if (tree[now].r==-1) { tree[now].r=++num; tree[num].l=tree[num].r=-1; } insert(tree[now].r,val,depth+1); } } ll findxor(int now,ll val,int depth) { if (depth==32) return 0; if ((val>>(31-depth))%2==0) { if (tree[now].l!=-1) return findxor(tree[now].l,val,depth+1)+(1<<(31-depth)); else return findxor(tree[now].r,val,depth+1); } else { if (tree[now].r!=-1) return findxor(tree[now].r,val,depth+1)+(1<<(31-depth)); else return findxor(tree[now].l,val,depth+1); } } int main() { int n,i,t,x,y; ll ans,d; while (scanf("%d",&n)!=EOF) { ans=num=0;memset(head,-1,sizeof(head)); for (i=1;i<n;i++) { scanf("%d%d%lld",&x,&y,&d); addedge(x,y,d); } mem0(visit); dfs(0,0); tree[0].l=tree[0].r=-1;num=0; for (i=0;i<n;i++) insert(0,a[i],0); for (i=0;i<n;i++) ans=max(ans,findxor(0,a[i],0)); printf("%lld\n",ans); } return 0; }