P4551 最长异或路径

题目描述

给定一棵\(n\)个点的带权树，结点下标从\(1\)开始到\(N\)。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入输出格式

输入格式：

第一行一个整数\(N\)，表示点数。

接下来 \(n-1\) 行，给出 \(u,v,w\) ，分别表示树上的 \(u\) 点和 \(v\) 点有连边，边的权值是 \(w\)。

输出格式：

一行，一个整数表示答案。

输入输出样例

输入样例#1： 复制

4

1 2 3

2 3 4

2 4 6

输出样例#1： 复制

说明

最长异或序列是1-2-3，答案是 7 (=3 ⊕ 4)

数据范围

\(1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31}\)

题解

字典树处理异或最大值模板题。

我们把每次数拆成01序列并且建字典树。

然后\(O(n)\)匹配每一个数字在字典树上的异或最大值，取最大的。

如何保证？我们是按从大到小的位数建的字典树，那么能选出1就选1.

每一个数字为建树时，该节点到根节点的异或值。

Code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<iostream>

using namespace std;

const int N=2e5+5;

int n,num,head[N],ch[N],tot;

int vis[N],ans;

struct node{

    int to,v,nex;

}e[N<<1];

struct tree{

    int ch[2];

}t[N*30];

int read(){

    int x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

void add(int from,int to,int v){

    num++;

    e[num].to=to;

    e[num].v=v;

    e[num].nex=head[from];

    head[from]=num;

}

void dfs(int x){

    for(int i=head[x];i;i=e[i].nex){

        int v=e[i].to;

        ch[v]=ch[x]^e[i].v;

        dfs(v);

    }

}

void build(int x){

    for(int i=0;i<=30;i++){

        if(x&(1<<i))vis[i]=1;

    }

    int now=0;

    for(int i=30;i>=0;i--){

        if(!t[now].ch[vis[i]])

            t[now].ch[vis[i]]=++tot;

        now=t[now].ch[vis[i]];

        vis[i]=0;

    }

}

void query(int x){

    for(int i=0;i<=30;i++)

        if(x&(1<<i))vis[i]=1;

    int now=0,sum=0;

    for(int i=30;i>=0;i--){

        if(t[now].ch[vis[i]^1])

            now=t[now].ch[vis[i]^1],sum+=(1<<i);

        else now=t[now].ch[vis[i]];

        vis[i]=0;

    }ans=max(ans,sum);

}

int main(){

    n=read();

    for(int i=1;i<n;i++){

        int x=read(),y=read(),z=read();

        add(x,y,z);//add(y,x,z);

    }dfs(1);

    for(int i=1;i<=n;i++)build(ch[i]);

    for(int i=1;i<=n;i++)query(ch[i]);

    cout<<ans<<endl;

    return 0;

}

巴特西

[luogu] P4551 最长异或路径（贪心）