P4551 最长异或路径
最长异或路径
题目描述
给定一棵 n n n 个点的带权树,结点下标从 1 1 1 开始到 n n n。寻找树中找两个结点,求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 n n n,表示点数。
接下来 n − 1 n-1 n−1 行,给出 u , v , w u,v,w u,v,w ,分别表示树上的 u u u 点和 v v v 点有连边,边的权值是 w w w。
输出格式
一行,一个整数表示答案。
样例 #1
样例输入 #1
4
1 2 3
2 3 4
2 4 6
样例输出 #1
7
提示
最长异或序列是 1 , 2 , 3 1,2,3 1,2,3,答案是 7 = 3 ⊕ 4 7=3\oplus 4 7=3⊕4。
数据范围
1 ≤ n ≤ 100000 ; 0 < u , v ≤ n ; 0 ≤ w < 2 31 1\le n \le 100000;0 < u,v \le n;0 \le w < 2^{31} 1≤n≤100000;0<u,v≤n;0≤w<231。
插入

代码:
//每条路径 <a,b> 的 xor 和转化成 “(a 到根的 xor 和) xor (b 到根的 xor 和)”
#include<bits/stdc++.h>
using namespace std;
struct node{int left=0,right=0;
}root;
vector<node> trie;
vector<int> a[100001],b[100001];//连接情况记录在a数组,权重情况记录在b数组
int yihuo[100005];//搜索异或值的结果
//通过dfs搜出所有节点到根节点的异或值
void dfs(int x,int y){//x代表节点,y代表当前的异或值是多少for(int i=0;i<a[x].size();i++){yihuo[a[x][i]]=y^b[x][i];//当前异或值异或连接到的节点的权重dfs(a[x][i],yihuo[a[x][i]]);//继续往下搜}
}
//生成01字典树
void build(int x){//记录各个节点的左右节点编号,这里默认左节点储存0,右节点储存1int fa=0,len;//每次重新输入一个异或值生成01树的时候fa都要重新置0for(int i=(1<<30);i>0;i>>=1){//边的权值最大为2的31次方,说明边权的异或最大值也是len=trie.size();//树的节点if(x&i){//当前位为1,遍历右边的if(trie[fa].right==0){//没有右节点trie[fa].right=len;// cout<<fa<<" right "<<len<<endl;trie.push_back(root);//把空节点push_back进去fa=len;//下一次的父节点为当前的节点编号}else fa=trie[fa].right; }else{//当前位为0,遍历左边的if(trie[fa].left==0){//没有左节点trie[fa].left=len;//给左节点编号// cout<<fa<<" left "<<len<<endl;trie.push_back(root);fa=len;}else fa=trie[fa].left;}}
}
int jisuan(int x){int ans=0,fa=0;cout<<x<<endl;for(int i=(1<<30);i>0;i>>=1){//i的初始值为1<<30是因为边的权值最大为2的31次方if(x&i){//当前位为1,由于是要求最长的异或路径,所以需要遍历左边的0,才能使得当前值为1if(trie[fa].left){ans+=i;// cout<<"left "<<ans<<" "<<trie[fa].left<<endl;fa=trie[fa].left;}else fa=trie[fa].right;}else{//当前位为0,由于是要求最长的异或路径,所以需要遍历右边的1,才能使得当前值为1if(trie[fa].right){ans+=i;// cout<<"right "<<ans<<" "<<trie[fa].right<<endl;fa=trie[fa].right;}else fa=trie[fa].left;}}// cout<<x<<" "<<ans;return ans;
}
void lesson1(){int n,x,y,z,ans=0;cin>>n;for(int i=1;i<n;i++){cin>>x>>y>>z;a[x].push_back(y);b[x].push_back(z);}dfs(1,0);trie.push_back(root);//0号节点,其左节点为0号节点,右节点为0号节点for(int i=1;i<=n;i++){build(yihuo[i]);// cin>>x;// cout<<x<<endl;// build(x); }for(int i=1;i<=n;i++){ans=max(ans,jisuan(yihuo[i]));}cout<<ans<<endl; // for(int i=1;i<=n;i++){// cout<<i<<":";// for(int j=0;j<a[i].size();j++)cout<<a[i][j]<<","<<b[i][j]<<" ";// cout<<endl;// }// for(int i=1;i<=n;i++)cout<<yihuo[i]<<" ";//根据题目样例得到0 3 7 5// for(int i=0;i<trie.size();i++){// cout<<i<<":"<<trie[i].left<<","<<trie[i].right<<endl;// }
}
int main(){lesson1();return 0;
}
相关文章:
P4551 最长异或路径
最长异或路径 题目描述 给定一棵 n n n 个点的带权树,结点下标从 1 1 1 开始到 n n n。寻找树中找两个结点,求最长的异或路径。 异或路径指的是指两个结点之间唯一路径上的所有边权的异或。 输入格式 第一行一个整数 n n n,表示点数…...
鸿蒙OpenHarmony HDF 驱动开发
目录 序一、概述二、HDF驱动框架三、驱动程序四、驱动配置坚持就有收获 序 最近忙于适配OpenHarmonyOS LiteOS-M 平台,已经成功实践适配平台GD32F407、STM32F407、STM32G474板卡,LiteOS适配已经算是有实际经验了。 但是,鸿蒙代码学习进度慢下…...
深度学习:如何面对隐私和安全方面的挑战
深度学习技术的广泛应用推动了人工智能的快速发展,但同时也引发了关于隐私和安全的深层次担忧。如何在保护用户隐私的同时实现高效的模型训练和推理,是深度学习领域亟待解决的问题。差分隐私、联邦学习等技术的出现,为这一挑战提供了可能的解…...
【操作系统概念】第12章:大容量存储阶段
文章目录 0.前言12.1 概述12.2磁盘结构12.3 磁盘调度12.3.1 FCFS调度12.3.2 SSTF调度12.3.3 SCAN调度12.3.4 C-SCAN调度12.3.5 如何选择磁盘调度 0.前言 文件系统从逻辑上来看包括三部分。第10章讨论了文件系统的用户和程序员的接口。第11章描述了操作系统实现这种接口的内部数…...
UE5.1_使用技巧(常更)
UE5.1_使用技巧(常更) 1. 清除所有断点 运行时忘记蓝图中的断点可能会出现运行错误的可能,务必运行是排除一切断点,逐个排查也是办法,但是在事件函数多的情况下会很复杂且慢节奏,学会一次性清除所有很有必…...
rust开发100问?
Rust如何管理内存?Rust的所有权是什么?生命周期在Rust中如何工作?什么是借用在Rust中?如何在Rust中创建枚举类型?Rust中的trait是什么?如何定义并实现一个结构体(struct)的方法&…...
.net6Api后台+uniapp导出Excel
之前的这个是vue3写法,后端是.net6Api.net6Api后台VUE3前端实现上传和下载文件全过程_vue3 下载文件-CSDN博客 在现在看来似乎搞的复杂了,本次记录一下.net6Api后台uniapp导出Excel。 后端和之前的不一样,前端也和之前的不一样,…...
【OD】算法二
开源项目热度榜单 某个开源社区希望将最近热度比较高的开源项目出一个榜单,推荐给社区里面的开发者。对于每个开源项目,开发者可以进行关注(watch)、收藏(star)、fork、提issue、提交合并请求(MR)等。 数据库里面统计了每个开源项目关注、收藏、fork、…...
《深度学习风暴:掀起智能革命的浪潮》
在当今信息时代,深度学习已经成为科技领域的一股强大力量,其应用领域涵盖了从医疗到金融再到智能交互等方方面面。随着技术的不断进步和应用的不断拓展,深度学习的发展势头愈发迅猛,掀起了一股智能革命的浪潮。本文将从基本原理、应用实例、挑战与未来发展方向、与机器学习…...
Arduin ESP32+epaper(电子墨水屏)时钟相册制作教程
Arduin ESP32 epaper(电子墨水屏)时钟相册制作教程 🔖epaper(电子墨水屏)采用的是:合宙1.54“ 电子墨水屏(e-paper)📍相关篇《Arduino框架下ESP32/ESP8266合宙1.54“ 电子墨水屏(e-paper)驱动显…...
Django模型层(附带test环境)
Django模型层(附带test环境) 目录 Django模型层(附带test环境)连接数据库Django ORM在models.py中建表允许为空指定默认值数据库迁移命令 开启测试环境建表语句补充(更改默认表名)数据的增加时间数据的时区 多表数据的增加一对多多对多 数据的删除修改数据查询数据查询所有数据…...
(AliyunAIACP17)知识点:神经网络(深度学习)分析
摘要: 案,详细阐述了神经网络的实现步骤,并提供了相应的代码示例。此外,文章还涵盖了神经网络中的技巧与实践、性能优化与测试,以及常见问题与解答。最后,对神经网络在深度学习中的应用前景进行了展望。 …...
基于 HBase Phoenix 构建实时数仓(1)—— Hadoop HA 安装部署
目录 一、主机规划 二、环境准备 1. 启动 NTP 时钟同步 2. 修改 hosts 文件 3. 配置所有主机间 ssh 免密 4. 修改用户可打开文件数与进程数(可选) 三、安装 JDK 四、安装部署 Zookeeper 集群 1. 解压、配置环境变量 2. 创建配置文件 3. 创建新…...
XS2185:八通道PSE控制器产品
八通道PSE控制器产品-XS2185 芯片特性 八通道PSE 支持标准PD供电 支持非标PD供电 每个端口功率最大30W 12位端口电流监测 12位电源电压监测 支持直流负载断开检测 支持LED供电状态指示 支持过流保护 支持短路保护 Sifos基本测试通过 32-PIN…...
Selenium WebDriver API 中涉及的一些常用方法和类
Selenium WebDriver API 是 Selenium 提供的一组方法和类,用于控制浏览器和操作 Web 元素。这些 API 提供了丰富的功能,包括但不限于: 1. **查找元素**:通过不同的定位方式(如ID、Class Name、XPath等)在页…...
OJ_复数集合
题干 C实现 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <queue> #include <string> using namespace std;struct Complex {int re;int im;//构造函数Complex(int _re, int _im) {//注意参数名字必须不同re _re;im _im;} };//结构体不支…...
【学一点RISC-V】ACLINT(高级核心本地中断控制器)文档
RISCV架构 ACLINT文档 ACLINT原文档:https://github.com/riscv/riscv-aclint/blob/main/riscv-aclint.adoc 在这里进行了翻译以及校对,仅供参考,不正确的地方欢迎指出 1、介绍 【此 RISC-V ACLINT 规范定义了一组内存映射设备,这…...
grafana table合并查询
注:本文基于Grafana v9.2.8编写 1 问题 默认情况下table展示的是一个查询返回的多个field,但是我想要的数据在不同的metric上,比如我需要显示某个pod的读写IO,但是读和写这两个指标存在于两个不同的metirc,需要分别查…...
编程笔记 html5cssjs 007 文章排版 颜真卿《述张长史笔法十二意》
编程笔记 html5&css&js 007 文章排版 颜真卿《述张长史笔法十二意》 一、代码二、解释 这段代码定义了一个古文展示页面的结构和样式,同时本文内容也是书法爱好者的珍贵资料。 一、代码 <!DOCTYPE html> <html lang"zh-CN"> <hea…...
Yolov8模型用torch_pruning剪枝
目录 🚀🚀🚀订阅专栏,更新及时查看不迷路🚀🚀🚀 原理 遍历所有分组 高级剪枝器 🚀🚀🚀订阅专栏,更新及时查看不迷路🚀🚀…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
