null - 程序员宅基地

前缀树 java map容器实现_poj-3764 The xor-longest Path（字典树）-程序员宅基地

技术标签：前缀树 java map容器实现

The xor-longest PathTime Limit: 2000MSMemory Limit: 65536K

Total Submissions: 13198Accepted: 2566

Description

In an edge-weighted tree, the xor-length of a path p is defined as the xor sum of the weights of edges on p:

⊕ is the xor operator.

say a path the xor-longest path if it has the largest xor-length. Given

an edge-weighted tree with n nodes, can you find the xor-longest path?

Input

The input contains several test cases. The first line of each test case contains an integer n(1<=n<=100000), The following n-1 lines each contains three integers u(0 <= u < n),v(0 <= v < n),w(0 <= w < 2^31), which means there is an edge between node u and v of length w.

Output

For each test case output the xor-length of the xor-longest path.

Sample Input4

0 1 3

1 2 4

1 3 6

Sample Output7

Hint

The xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)

题意：

给你一棵树，求一段路径(连续)使得边权相异或的结果最大。

题解：

直接01字典的板子题。利用的性质是求x->y的异或值就是 (root->x ^ root->y)，然后相当于dfs暴力。#include

#include

#define inf 0x3f3f3f3f

#define ll long long

#define sscc ios::sync_with_stdio(false);

#define ms(a) memset(a,0,sizeof(a))

#define mss(a) memset(a,-1,sizeof(a))

#define msi(a) memset(a,inf,sizeof(a))

using namespace std;

const int N=1e6+5;

struct node{

int y,len,next;

}a[N<<1];

int pre[N],cnt;

void add(int x,int y,int z){

a[cnt].y=y,a[cnt].len=z,a[cnt].next=pre[x];

pre[x]=cnt++;

}

struct Tire{

int ch[N*32][2],vu[N*32],tol;

void init(){

tol=0;

vu[0]=0;

ms(ch[0]);

}

int newnode()//新建节点{

ms(ch[++tol]);

vu[tol]=0;

return tol;

}

void insert(int x)//插入{

int s=0;

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

int k=(x>>i)&1;

if(!ch[s][k])ch[s][k]=newnode();

s=ch[s][k];

vu[s]++;

}

int query(int x)//查询与x异或后最大的数{

int su=0,s=0;

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

int k=(x>>i)&1;

if(vu[ch[s][!k]])su|=1<

elses=ch[s][k];

}

return x;

}

}t1;

int ans;

void dfs(int x,int fa,int val){//两条路径重叠抵消

t1.insert(val);

for(int i=pre[x];~i;i=a[i].next){

int y=a[i].y,len=a[i].len;

if(y==fa)continue;

ans=max(ans,t1.query(val^len));

dfs(y,x,val^len);//累计

}

int main(){

int n;

while(~scanf("%d",&n))

{

mss(pre);cnt=0;

t1.init(),ans=0;

for(int i=1;i

int x,y,z;

scanf("%d%d%d",&x,&y,&z);

add(x,y,z);

add(y,x,z);

}

dfs(0,-1,0);

printf("%d\n",ans);

}

return 0;

}

本文链接：https://blog.csdn.net/weixin_39811166/article/details/114938544

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

HTML5 Web SQL 数据库_方式准则的定义-程序员宅基地

文章浏览阅读1k次。1、HTML5 Web SQL 数据库 Web SQL 数据库 API 并不是 HTML5 规范的一部分，但是它是一个独立的规范，引入了一组使用 SQL 操作客户端数据库的 APIs。如果你是一个 Web 后端程序员，应该很容易理解 SQL 的操作。Web SQL 数据库可以在最新版的 Safari, Chrome 和 Opera 浏览器中工作。2、核心方法以下是规范中定义的三个_方式准则的定义

spring Boot 中使用线程池异步执行多个定时任务_springboot启动后自动开启多个线程程序-程序员宅基地

文章浏览阅读4.1k次，点赞2次，收藏6次。spring Boot 中使用线程池异步执行多个定时任务在启动类中添加注解@EnableScheduling配置自定义线程池在启动类中添加注解@EnableScheduling第一步添加注解，这样才会使定时任务启动配置自定义线程池@Configurationpublic class ScheduleConfiguration implements SchedulingConfigurer..._springboot启动后自动开启多个线程程序

Maven编译打包项目 mvn clean install报错ERROR_mvn clean install有errors-程序员宅基地

文章浏览阅读1.1k次。在项目的target文件夹下把之前"mvn clean package"生成的压缩包(我的是jar包)删掉重新执行"mvn clean package"再执行"mvn clean install"即可_mvn clean install有errors

navacate连接不上mysql_navicat连接mysql失败怎么办-程序员宅基地

文章浏览阅读974次。Navicat连接mysql数据库时，不断报1405错误，下面是针对这个的解决办法：MySQL服务器正在运行，停止它。如果是作为Windows服务运行的服务器，进入计算机管理--->服务和应用程序------>服务。如果服务器不是作为服务而运行的，可能需要使用任务管理器来强制停止它。创建1个文本文件(此处命名为mysql-init.txt)，并将下述命令置于单一行中：SET PASSW..._nvarchar链接不上数据库

Python的requests参数及方法_python requests 参数-程序员宅基地

文章浏览阅读2.2k次。Python的requests模块是一个常用的HTTP库，用于发送HTTP请求和处理响应。_python requests 参数

近5年典型的的APT攻击事件_2010谷歌网络被极光黑客攻击-程序员宅基地

文章浏览阅读2.7w次，点赞7次，收藏50次。APT攻击APT攻击是近几年来出现的一种高级攻击，具有难检测、持续时间长和攻击目标明确等特征。本文中，整理了近年来比较典型的几个APT攻击，并其攻击过程做了分析（为了加深自己对APT攻击的理解和学习）Google极光攻击2010年的Google Aurora(极光)攻击是一个十分著名的APT攻击。Google的一名雇员点击即时消息中的一条恶意链接，引发了一系列事件导致这个搜_2010谷歌网络被极光黑客攻击

随便推点

微信小程序api视频课程-定时器-setTimeout的使用_微信小程序 settimeout 向上层传值-程序员宅基地

文章浏览阅读1.1k次。JS代码 /** * 生命周期函数--监听页面加载 */ onLoad: function (options) { setTimeout( function(){ wx.showToast({ title: '黄菊华老师', }) },2000 ) },说明该代码只执行一次..._微信小程序 settimeout 向上层传值

uploadify2.1.4如何能使按钮显示中文-程序员宅基地

文章浏览阅读48次。uploadify2.1.4如何能使按钮显示中文博客分类：uploadify网上关于这段话的搜索恐怕是太多了。方法多也试过了不知怎么，反正不行。最终自己想办法给解决了。当然首先还是要有fla源码。直接去管网就可以下载。[url]http://www.uploadify.com/wp-content/uploads/uploadify-v2.1.4...

戴尔服务器安装VMware ESXI6.7.0教程（U盘安装）_vmware-vcsa-all-6.7.0-8169922.iso-程序员宅基地

文章浏览阅读9.6k次，点赞5次，收藏36次。戴尔服务器安装VMware ESXI6.7.0教程（U盘安装）一、前期准备1、下载镜像下载esxi6.7镜像：VMware-VMvisor-Installer-6.7.0-8169922.x86_64.iso这里推荐到戴尔官网下载，Baidu搜索“戴尔驱动下载”，选择进入官网，根据提示输入服务器型号搜索适用于该型号服务器的所有驱动下一步选择具体类型的驱动选择一项下载即可待下载完成后打开软碟通（UItraISO），在“文件”选项中打开刚才下载好的镜像文件然后选择启动_vmware-vcsa-all-6.7.0-8169922.iso

前缀树 java map容器实现_poj-3764 The xor-longest Path（字典树）-程序员宅基地

智能推荐

HTML5 Web SQL 数据库_方式准则的定义-程序员宅基地

spring Boot 中使用线程池异步执行多个定时任务_springboot启动后自动开启多个线程程序-程序员宅基地

Maven编译打包项目 mvn clean install报错ERROR_mvn clean install有errors-程序员宅基地

navacate连接不上mysql_navicat连接mysql失败怎么办-程序员宅基地

Python的requests参数及方法_python requests 参数-程序员宅基地

近5年典型的的APT攻击事件_2010谷歌网络被极光黑客攻击-程序员宅基地

随便推点

微信小程序api视频课程-定时器-setTimeout的使用_微信小程序 settimeout 向上层传值-程序员宅基地

uploadify2.1.4如何能使按钮显示中文-程序员宅基地

戴尔服务器安装VMware ESXI6.7.0教程（U盘安装）_vmware-vcsa-all-6.7.0-8169922.iso-程序员宅基地

百度语音技术永久免费的语音自动转字幕介绍 -程序员宅基地

Dyninst学习笔记-程序员宅基地

在服务器上部署asp网站,部署asp网站到云服务器-程序员宅基地

推荐文章

热门文章

相关标签