Fork me on GitHub

POJ3764--The xor-longest Path

发表于 | | 阅读次数:
字数统计: 585

传送门：POJ3764—The xor-longest Path

题目大意:在一颗带权的树上，求任意两点间路径上各边权值异或和的最大值。

题目解法：设dis(u,v)为u,v间路径上各边权值异或和。

显然dis(u,v)==dis(root,u)^dis(root,v),所以问题转换为求任意两个点i,j到root的路径上各边权值异或和最大。

于是我们用dfs预处理，把每个dis(root,i)丢进一个二进制trie中。

那每丢一个dis(root,i)，显然要在trie中找能使尽量多的二进制位与dis(root,i)相反，这样才能使这两个的异或和最大，这其实就是个贪心。

真相は一つしかない: 正解就是trie+贪心（逃

嗯♂~~~代码实现如下：

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>
#define ll long long
#define maxn 100005
using namespace std;
int N;
int _last[maxn],_next[maxn<<1],_end[maxn<<1],_len[maxn<<1];
int val[maxn];
int o;
int tot;
void ins(int a,int b,int c){
	_end[++o]=b;
	_next[o]=_last[a];
	_last[a]=o;
	_len[o]=c;
}
void inss(int a,int b,int c){
	ins(a,b,c);
	ins(b,a,c);
}
struct node{
	int son[2];
	void init(){
		son[0]=son[1]=0;
	}
};
node tri[4000005];
void dfs(int u,int fa){
	for(int i=_last[u];i;i=_next[i]){
		int v=_end[i];
		if(v==fa)continue;
		val[v]=val[u]^_len[i];
		dfs(v,u);
	}
}
void add(int x){
	int p=0;
	int o=0;
	for(int i=30;i>=0;--i){
		if(x&(1<<i))o=1;
		else o=0;
		if(!tri[p].son[o]){
			tri[p].son[o]=++tot;
			tri[tot].init();
		}
		p=tri[p].son[o];
	}
}
int gs(int x){
	int num=0,p=0,o=0;
	for(int i=30;i>=0;--i){
		if(x&(1<<i))o=0;
		else o=1;
		if(tri[p].son[o]){
			num|=(1<<i);
			p=tri[p].son[o];
		}
		else p=tri[p].son[o^1];
	}
	return num;
}
int main(){
	while(scanf("%d",&N)!=EOF){
		for(int i=1;i<=o;++i)_last[i]=0;
		o=0;
		tot=0;
		tri[tot].init();
		val[1]=0;
		int u,v,w;
		for(int i=1;i<N;++i) {
			scanf("%d%d%d",&u,&v,&w);
			++u;
			++v;
			inss(u,v,w);
		}
		dfs(1,0);
		int ans=0;
		for(int i=1;i<=N;++i){
			ans=max(ans,gs(val[i]));
			add(val[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}
0%
``` ```