洛谷P4551 最长异或路径

@Pelom  October 31, 2019

题意

给出一棵$n$个点的带权树,求最长异或路径

数据范围:$1 \le n \le 100000,1 \le w < 2^{31}$

题解

由于$\text{xor}$是自己的逆运算,因此可以得到一个结论:树上任意$1$条路径可由$2$条从根节点出发的路径$\text{xor}$得来
假设以$1$为根节点,先$\text{dfs}$对于每个点求出到$1$节点的路径
其次,求解$\text{xor}$问题常用$01$字典树$\text{trie}$;那么,将处理好的路径加入字典树,再在$01$字典树上对每一条路径贪心地求与其$\text{xor}$的最大值

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100000+10;
int n,u,v,w;
int cnt,ans,tot;
int head[N],dis[N];
struct edge{
    int nxt,to,w;
} e[N<<1];
struct Trie{
    int T[N<<5][2];
    inline Trie(){
        memset(T,0,sizeof(T));
    }
    inline void insert(int x){
        int a=0;
        for(int i=1<<30;i;i>>=1){
            bool b=x&i;
            if(!T[a][b])
                T[a][b]=++tot;
            a=T[a][b];
        }
    }
    inline int query(int x){
        int res=0,a=0;
        for(int i=1<<30;i;i>>=1){
            bool b=x&i;
            if(T[a][b^1]){
                res+=i;
                a=T[a][b^1];
            }
            else a=T[a][b];
        }
        return res;
    }
} trie;
inline void add(int u,int v,int w){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
void dfs(int u,int f){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==f)
            continue;
        dis[v]=dis[u]^e[i].w;
        dfs(v,u);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        trie.insert(dis[i]);
    for(int i=1;i<=n;i++)
        ans=max(ans,trie.query(dis[i]));
    printf("%d",ans);
    return 0;
}

添加新评论