01字典树之求树上最长异或路径

深藏阁楼爱情的钟 2024-04-18 09:24 53阅读 0赞

**题目描述**

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

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

洛谷：4551  最长异或路径

思路，首先dfs处理出每个点到 根 的距离

然后将这些距离存在字典树中，然后对于每个距离查询字典树，得到最优值

注意：字典树一维空间大小。

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+50;
    struct node{int to,next,v;}e[M<<1];
    
    int n,head[M<<1],res,tot,cnt,t[M*35][5],xo[M];
    void add(int x,int y,int v){
        e[cnt].to=y;e[cnt].v=v;e[cnt].next=head[x];head[x]=cnt++;
        e[cnt].to=x;e[cnt].v=v;e[cnt].next=head[y];head[y]=cnt++;
    }
    void dfs(int x,int fa){
        for(int to,i=head[x];~i;i=e[i].next){
            to=e[i].to;
            if(to==fa)continue;
            xo[to]=xo[x]^e[i].v;
            dfs(to,x);
        }
    }
    void build(int x){
        int now=0;
        for(int i=1<<30;i;i>>=1){
            bool k=x&i;
            if(!t[now][k])t[now][k]=++tot;
            now=t[now][k];
        }
    }
    int  query(int x){
        int now=0,ans=0;
        for(int i=1<<30;i;i>>=1){
            bool c=x&i;
            if(t[now][c^1])ans+=i,now=t[now][c^1];
            else now=t[now][c];
        }
        return ans;
    }
    int main(){
        memset(head,-1,sizeof(head));cnt=1;
        scanf("%d",&n);
        for(int x,y,v,i=1;i<n;i++)scanf("%d%d%d",&x,&y,&v),add(x,y,v);
        dfs(1,0);
        for(int i=1;i<=n;i++)build(xo[i]);
        for(int i=1;i<=n;i++)res=max(query(xo[i]),res);
        printf("%d",res);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，53人围观）

还没有评论，来说两句吧...

相关阅读

相关 01字典树之求树上最长异或路径

*题目描述** 给定一棵 n 个点的带权树，结点下标从 1 开始到 N 。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异...

深藏阁楼爱情的钟/ 2024年04月18日 09:24/ 0 赞/ 54 阅读

相关二叉树之最长同值路径

二叉树之最长同值路径问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0

太过爱你忘了你带给我的痛/ 2023年10月06日 08:01/ 0 赞/ 54 阅读

相关 LuoGuP4551最长异或路径

[LuoGuP4551最长异或路径][LuoGuP4551] \\(01Trie\\)裸题,懒得写\\(solution\\)了,直接贴代码吧,好懒啊yyy. \\(C

以你之姓@/ 2023年06月02日 11:58/ 0 赞/ 3 阅读

相关二叉树之求二叉树中最大路径和

LeetCode中一道求二叉树中最大路径和的题目，一起来复习下二叉树的遍历。以如图所示二叉树为例 ![在这里插入图片描述][2020060215091962.bmp]

朱雀/ 2023年02月14日 10:41/ 0 赞/ 152 阅读

相关【LeetCode】﹝前缀树ி﹞最长单词、键值映射、最大异或值

【LeetCode】﹝前缀树ி﹞最长单词、键值映射、最大异或值文章目录【LeetCode】﹝前缀树ி﹞最长单词、键值映射、最大异或值

布满荆棘的人生/ 2022年10月05日 13:46/ 0 赞/ 160 阅读

相关 CSU oj 1681 Adjoin（dfs求树上最长路径）（搜索）

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1681 题目大意：给你一共有n个结点但是不连通的无向图，你需要用

拼搏现实的明天。/ 2022年08月21日 12:44/ 0 赞/ 147 阅读

相关二叉树求最短路径

include<iostream> include<stdlib.h> using namespace std; template <class

痛定思痛。/ 2022年06月14日 10:22/ 0 赞/ 250 阅读

相关 HDU5536 01字典树求模板

include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct T

傷城~/ 2022年05月09日 05:18/ 0 赞/ 199 阅读

相关二叉树最长路径

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1

╰+攻爆jí腚メ/ 2022年04月15日 00:36/ 0 赞/ 241 阅读

相关 143. 最大异或对(字典树 + 位运算)

题目描述：在给定的N个整数A1，A2……AN 中选出两个进行xor（异或）运算，得到的结果最大是多少？输入格式第一行输入一个整数N。第二行输入N个整数A

刺骨的言语ヽ痛彻心扉/ 2021年12月05日 21:43/ 0 赞/ 272 阅读