【trie】The xor-longest Path

字典树

传送门：POJ3764

题意：树上最大异或和路径

思路：求出根到所有点的路径的异或值，然后从高到低放入字典树，然后枚举验证

以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 150000
int n,x,y,z,tot,tot_edge,dist[N],son[N*32][2],head[N];
struct edge{int v,dist,nxt;}e[N*3];
void init(){
	tot=1; tot_edge=0;
	memset(head,0,sizeof head); memset(e,0,sizeof e);
	memset(dist,-1,sizeof dist); memset(son,0,sizeof son);
}
void add(int x,int y,int z){
	e[++tot_edge].v=y; e[tot_edge].dist=z; e[tot_edge].nxt=head[x]; head[x]=tot_edge;
	e[++tot_edge].v=x; e[tot_edge].dist=z; e[tot_edge].nxt=head[y]; head[y]=tot_edge;
}
void dfs(int x,int d){
	dist[x]=d;
	for (int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if (dist[v]==-1) dfs(v,d^e[i].dist);
	}
}
int query(){
	int ans=0;
	for (int i=0;i<n;i++){
		int x=1,sum=0;
		for (int j=30;j>=0;j--)
			if ((1<<j)&dist[i]){
				if (son[x][0]){x=son[x][0]; sum+=1<<j;} else x=son[x][1];
			}
			else{
				if (son[x][1]){x=son[x][1]; sum+=1<<j;} else x=son[x][0];
			}
		ans=max(ans,sum);
	}
	return ans;
}
int main(){
	while (~scanf("%d",&n)){
		init();
		for (int i=1;i<n;i++){scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);}
		dfs(0,0);
		for (int i=0;i<n;i++){
			int x=1;
			for (int j=30;j>=0;j--)
				if ((1<<j)&dist[i]){
					if (!son[x][1]) son[x][1]=++tot;
					x=son[x][1];
				}
				else{
					if (!son[x][0]) son[x][0]=++tot;
					x=son[x][0];
				}
		}
		printf("%d\n",query());
	}
	
	return 0;
}