最长异或值路径

题目

给定一个树,树上的边都具有权值。

树中一条路径的异或长度被定义为路径上所有边的权值的异或和:

给定上述的具有n个节点的树,你能找到异或长度最大的路径吗?

输入格式

第一行包含整数n,表示树的节点数目。

接下来n-1行,每行包括三个整数u,v,w,表示节点u和节点v之间有一条边权重为w。

输出格式

输出一个整数,表示异或长度最大的路径的最大异或和。

数据范围

1≤n≤100000,
0≤u,v<n,
0≤w<231

输入样例:

4
0 1 3
1 2 4
1 3 6

输出样例:

7

样例解释

样例中最长异或值路径应为0->1->2,值为7 (=3 ⊕ 4)

分析:

  • 这个题和求最大异或对的题很相似,只是他求的是一条路径上的最大异或值。
  • 最大异或对链接:https://blog.csdn.net/qq_41934571/article/details/98467863
  • 我们知道相同值异或的结果是零,并且与零异或值不变,因此我们,可以先假设某一点为根节点,用深搜求出所有点到他的异或路径值a[i]。
  • 那么我们发现对两个叶节点a[i]和a[j]异或的值,就是i到j的异或路径值。因为他们到根节点的那一段是相同的,或者他们的路径就是一起到根节点路径的和。那么相同的异或以后就会零,因此两个叶节点a[i]和a[j]异或的值,就是i到j的异或路径值。
  • 那么这个题就成功的转化为了求两个最大异或对的题。

代码:

#include <iostream>
using namespace std;
const int N=1e5+5,NN=2e5+5,M=3e6,bitsum=30;

int head[N],tot;
struct egde{
    int to,w;
    int next;
}edge[NN];

//链式前向星 
void add(int x,int y,int w){ 
    edge[++tot].to=y;
    edge[tot].w=w;
    edge[tot].next=head[x];
    head[x]=tot;
}

int p[N],vis[N];
int trie[M][2],idx;
int n,m;

//深搜求所有节点到根节点的异或值 
void dfs(int x,int sum){
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        int temp=edge[i].to,kk=edge[i].w;
        if(!vis[temp]) {
            p[temp]=sum^kk;
            dfs(temp,sum^kk);
        }
    }
}

//trie树插入 
void trie_insert(int x){
    int p=0;
    for(int i=bitsum;~i;i--){
        int &s=trie[p][x>>i&1];
        if(!s) s=++idx;
        p=s;
    }
}

//trie查询 
int trie_search(int x){
    int p=0;
    int ans=0;
    for(int i=bitsum;~i;i--){
        int s=x>>i&1;
        if(trie[p][!s]){
            ans+=1<<i;
            p=trie[p][!s];
        }else p=trie[p][s];
    }
    return ans;
}

int main()
{
    int x,y,w;
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>x>>y>>w;
        add(x,y,w);
        add(y,x,w);
    }
    dfs(0,0);
    int ans=0;
//    for(int i=0;i<n;i++){
//        cout<<p[i]<<" ";
//    }
    for(int i=0;i<n;i++){
        trie_insert(p[i]);
    }

    for(int i=0;i<n;i++){
        ans=max(ans,trie_search(p[i]));
    }
    cout<<ans<<endl;
    return 0;
}

   转载规则


《最长异或值路径》 蒋曾辉 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录