POJ3764 The xor-longest Path(字典树)

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

Output

Sample Input

4
0 1 3
1 2 4
1 3 6

Sample Output

7

Hint

• 题意：给一颗n个节点的树，树的每条边有权值，从中选出两个结点x、y，把x到y最短路径上的值异或起来，求最大的异或值。
  题解：对于一棵树的两个结点之间的路径异或最大值，如果用朴素方法的话，可能需要遍历C(n,2)次所有的节点。
  但是题目有明确的暗示，异或，异或符合交换律，并且a^a=0。树的节点到根节点的最短路径唯一，那么我们用d[i]表示节点i到根节点路径的异或值，两个节点路径之间的异或值就是d[i]^d[j]。
• 那么问题就转化为了与ch1602一样的问题，即选出两个数，异或值最大。
• 转化后的解法：
  • 先用dfs得出d[]
  • 每当输入一个d[i]，将这个数转化为32位的二进制数，从高位到低位放入字典树中，再进行一次查询，查询优先向该位异或值为1地方向进行。
• 需要注意的点
  1. 需要用邻接表来储存边权关系，且不能用vector版本的简易邻接表。
  2. 需要存正反边，然后用vis标记。
  3. 多种样例，需要对变量初始化。
  4. 需要自己的定义max。
  5. 不能用cin输入。

//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a%b) : a;
}
template <class T>
inline bool scan_d(T &ret) {
	char c;
	int sgn;
	if(c=getchar(),c==EOF) return 0; //EOF
	while(c!='?'&&(c<'0'||c>'9')) c=getchar();
	sgn=(c=='?')?-1:1;
	ret=(c=='?')?0:(c-'0');
	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
	ret*=sgn;
	return 1;
}
inline void outt(int x) {
	if(x>9) outt(x/10);
	putchar(x%10+'0');
}
template<class T>inline void gmax(T &A, T B){
	(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B){
	(A>B)&&(A=B);//if(B<A)A=B;
}
const int maxn=1e5+10;
int d[maxn];
int Base[40];
int vis[maxn];
int trie[maxn*40][2],tot=0;
struct Edge { //边结构
	int v,cost,next;    //储存边以及权
	Edge(int _v=0,int _cost=0,int _next=0):v(_v),cost(_cost),next(_next) {};
}edge[maxn<<1];
int p,head[maxn];
void addedge(int u,int v,int w) {
	edge[p].v=v,edge[p].cost=w,edge[p].next=head[u],head[u]=p++;
}

void into_base(int x) {
	int cnt=33;
	CLR(Base);
	while(x) {
		Base[--cnt]=x%2;
		x/=2;
	}
}

void insert() {
	int p=0;
	rep(i,1,32) {
		int ch=Base[i];
		if(trie[p][ch]==0)trie[p][ch]=++tot;
		p=trie[p][ch];
	}
}
int search() {
	int p=0;
	int cnt=0;
	rep(i,1,32) {
		cnt*=2;
		int ch=Base[i];
		if(trie[p][!ch]!=0) {
			ch=!ch;
			cnt++;
		}
		p=trie[p][ch];
	}
	return cnt;
}

void dfs(int u) {
	vis[u]=1;
	for(int i=head[u]; i!=-1; i=edge[i].next) {
		int v=edge[i].v;
		int w=edge[i].cost;
		if(!vis[v]) {
			d[v]=d[u]^w;
			dfs(v);
		}
	}
}
int main() {
	int n;
	while(~scanf("%d", &n)) {
		p=0;
		MST(head,-1);
		tot=0;
		CLR(d);
		CLR(trie);
		CLR(vis);
		int u,v,w;
		rep(i,1,n-1) {
			scan_d(u);
			scan_d(v);
			scan_d(w);
			addedge(u,v,w);
			addedge(v,u,w);
		}
		dfs(0);
		int maxx=0;
		rep(i,0,n-1) {
			into_base(d[i]);
			insert();
			gmax(maxx,search());
		}
		cout<<maxx<<endl;
	}

	return 0;
}