「POJ 3764」The xor-longest Path

Description

题目链接:POJ 3764

给定一棵有 $n$ 个节点的树,每条边有一个权值 $a_i$。你需要在树上找一条简单路径,使得这条路径上的边权异或和最大。

数据范围:$1\le n\le 10^5$,$0\le a_i<2^{31}$


Solution

首先我们对这个问题进行转化:设 $f(u,v)$ 表示从 $u$ 到 $v$ 的简单路径上的边权异或和。那么根据异或的性质,有 $f(u,v)=f(1,u)\oplus f(1,v)$,故问题转化为 $\max_{1\le i\le n,1\le j\le n}f(1,i)\oplus f(1,j)$,可以 $O(n^2)$ 解决,但是无法通过此题。

接下来考虑如何优化。这个式子的本质其实是:对于每一个 $f(1,i)$,找到一个 $f(1,j)$ 使得 $f(1,u)\oplus f(1,v)$ 最大。我们可以非常套路地贪心,使得答案的高位尽量为 $1$。对于每个点求出它到根的路径的异或和 $dis_i$ 并插入 $\text{Trie}$ 树,再对于每个 $dis_i$ 在 $\text{Trie}$ 树上找贪心地找到对应的 $dis_j$。

贪心策略:尽量在 $\text{Trie}$ 树上走和当前位不同的节点;如果没有,则只能妥协走当前节点仅有的儿子。

时间复杂度:$O(n\log a_i)$


Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=1e5+5,M=2e5+5;
int n,tot,lnk[N],ter[M],nxt[M],val[M];
int dis[N],idx,ch[30*N][2];

void add(int u,int v,int w) {
ter[++tot]=v,nxt[tot]=lnk[u],val[tot]=w,lnk[u]=tot;
}
void dfs(int u,int fa) {
for(int i=lnk[u];i;i=nxt[i]) {
int v=ter[i];
if(v==fa) continue;
dis[v]=dis[u]^val[i],dfs(v,u);
}
}
void ins(int x) {
int u=0;
for(int i=30;~i;--i) {
int b=(x>>i)&1;
if(!ch[u][b]) ch[u][b]=++idx,memset(ch[idx],0,sizeof(ch[idx]));
u=ch[u][b];
}
}
int query(int x) {
int u=0,ret=0;
for(int i=30;~i;--i) {
int b=(x>>i)&1;
if(ch[u][b^1]) u=ch[u][b^1],ret|=1<<i;
else u=ch[u][b];
}
return ret;
}
int main() {
while(~scanf("%d",&n)) {
memset(lnk,0,sizeof(lnk)),tot=idx=0;
for(int i=1;i<n;++i) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w),++u,++v;
add(u,v,w),add(v,u,w);
}
dfs(1,0);
int ans=0;
memset(ch[0],0,sizeof(ch[0]));
for(int i=1;i<=n;++i) ins(dis[i]);
for(int i=1;i<=n;++i) ans=std::max(ans,query(dis[i]));
printf("%d\n",ans);
}
return 0;
}
0%