「POJ 3764」The xor-longest Path

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

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%