前缀树 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

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

智能推荐

2014年高级计算机操作员工种代码36-323不可积分入户深圳吗,计算机操作员（2011年深圳招调工热门工种）...-程序员宅基地

文章浏览阅读198次。好消息：计算机操作员(工种代码：46-207)被确定为2011年深圳市职业技能鉴定计算机类鉴定工种学习对象：Office2003综合应用：1、向有一定电脑基础，特别是对OFFICE办公软件有一定了解，欲从事计算机日常办公的人员进行培训.2、此科目是深圳市招调工种.图形图像处理CorelDraw X3：1、从事或有意从事工艺美术、广告艺术、图文排版、图文印刷、计算机多媒体技术工作人员以及其他需要掌握..._计算机操作员职业代码

文心一言api接入如何在你的项目里使用文心一言_文言一心api-程序员宅基地

文章浏览阅读7.5k次，点赞6次，收藏47次。基于百度文心一言语言大模型的智能文本对话AI机器人API,支持聊天对话、行业咨询、语言学习、代码编写等功能.您的AppKey和uid是重要信息,请务必妥善保存,避免泄漏!您的AppKey和uid是重要信息,请务必妥善保存,避免泄漏!您的AppKey和uid是重要信息,请务必妥善保存,避免泄漏!AppKey申请通过后,登录。请求方式: POST。_文言一心api

别再用硬编码写业务流程了，试试这款轻量级流程编排框架-程序员宅基地

文章浏览阅读488次。前言在每个公司的系统中，总有一些拥有复杂业务逻辑的系统，这些系统承载着核心业务逻辑，几乎每个需求都和这些核心业务有关，这些核心业务业务逻辑冗长，涉及内部逻辑运算，缓存操作，持久化操作，外部..._什么业务场景要用到编排工具

P1015 回文数_1、若一个5位数字从左向右读与从右向左读都一样,我们就将其称之为回文串。小申编-程序员宅基地

文章浏览阅读297次。题目描述若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个十进制数5656，将5656加6565（即把5656从右向左读），得到121121是一个回文数。又如：对于十进制数8787：STEP1：8787+7878=165165STEP2：165165+561561=726726STEP3：726726+627627=13531..._1、若一个5位数字从左向右读与从右向左读都一样,我们就将其称之为回文串。小申编

直线与球体的交点lisp_晓东CAD家园-论坛-A/VLISP-[LISP函数]：计算直线与曲线交点-:5 如何用Lisp程序计算支线Line与曲线（二次样条或PLINE拟合曲线）三交点，请诸位高手提...-程序员宅基地

文章浏览阅读389次。[font=courier new]86. xdrx_getinters功能：1.求两个AcDbCurve(曲线)实体的交点.2.求一个AcDbCurve(曲线)实体和一个选择集中所有AcDbCurve(曲线)的交点。3.求一个选择集中所有AcDbCurve(曲线)实体的交点.4.求一个选择集SS1中的所有AcDbCurve实体和另个选择集SS2所有AcDbCurve实体的交点。调用格式： 1. ..._lisp inters

HDU 1198 - Farm Irrigation-程序员宅基地

文章浏览阅读44次。Problem DescriptionBenny has a spacious farm land to irrigate. The farm land is a rectangle, and is divided into a lot of samll squares. Water pipes are placed in these squares. Different square has...

随便推点

Axis2/c 知识点-程序员宅基地

文章浏览阅读145次。官网文档： http://axis.apache.org/axis2/c/core/docs/axis2c_manual.html从文档中可以总结出：1. Axis2/C是一个用C语言实现的Web Service引擎。Axis2/C基于Axis2架构，支持SOAP1.1和SOAP1.2协议，并且支持RESTful风格的Web Service。基于Axis2/C的Web Service可以..._axis2/c服务端调用axis2_get_instance

企业架构方法论-程序员宅基地

文章浏览阅读3k次。目前主要的两种架构方法（准确的说是方法论），具体的方法也是有的，也有可实际操作层面的东西，那要看很多的各个细分专业层面的东西。比如画流程图，业务流程图、数据流程图、系统交互流程图等等。togafzachmanzachman业务建模分析框架，相比于togaf，直观上直接提供了可操作的东西，可能大家更容易接受一些。这里推荐一个架构设计的专业工具，是免费的，即ArchMateArchi – Open Source ArchiMate Modelling (archim..._企业架构方法论

堆栈与队列的方法区分、优先队列的应用_判断是栈还是队列还是优先队列-程序员宅基地

文章浏览阅读123次。堆栈与队列具体的方法区分_判断是栈还是队列还是优先队列

上海计算机学会2021年7月月赛C++丙组T1布置会场-程序员宅基地

文章浏览阅读352次，点赞8次，收藏8次。小爱老师可以购买两份双拼花束后，将他重新组合成一束百合花+一束郁金香。已知布置会场需要用到x束百合花与y束郁金香，请问小爱老师购买花朵最少花费需多少元？输出共一行，一个正整数，表示小爱老师购买花朵最少花费需多少元。直接购买8束百合+6束郁金香，共计8*8+6*10=124元。内存限制: 256 Mb时间限制: 1000 ms。先购买12束双拼花朵，花费12*8=96元，第一行：两个正整数表示需要的花束数量x,y。第二行：三个正整数表示花束费用a,b,c。再购买2束百合花，花费2*8=16元，

python实现ping某一ip_使用Python测试Ping主机IP和某端口是否开放的实例-程序员宅基地

文章浏览阅读518次。使用Python方法比用各种命令方便，可以设置超时时间，到底通不通，端口是否开放一眼能看出来。命令和返回完整权限，可以ping通，端口开放，结果如下：无root权限(省略了ping)，端口开放，结果如下：完整权限，可以ping通，远端端口关闭，结果如下：完整权限，可以ping通，本地端口关闭，结果如下：完整权限，不能ping通(端口自然也无法访问)，结果如下：pnp.py代码#!/usr/bin/..._python ping ip无管理员权限

zplane函数怎么用m文件调用_matlab中cla用法-程序员宅基地

文章浏览阅读738次。零极点与系统稳定性的关系 4.状态方程含义 5.使用 zplane 函数 [实验原理] 该实验用 MATLAB 中库函数,如 tf2zp(b,a),ss2zp(A,B,C,D),zplane(z,p),......MATLAB 中相关命令 aa abs 绝对值、模、字符的 ascii 码值 a...零极点与系统稳定性的关系 4.状态方程含义 5.使用 zplane 函数 [实验原理] 该实验用 M..._matlabcla。m文件