博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 3764 The xor-longest Path (01 Trie)
阅读量:4616 次
发布时间:2019-06-09

本文共 2306 字,大约阅读时间需要 7 分钟。

链接:http://poj.org/problem?id=3764

题面:

The xor-longest Path
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 11802   Accepted: 2321

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:

_{xor}length(p)=\oplus_{e \in p}w(e)

⊕ is the xor operator.

We 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 Input

40 1 31 2 41 3 6

Sample Output

7

Hint

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

 

思路;

树上dfs一遍跟区间差不多的写法

 

实现代码;

#include
#include
#include
using namespace std;#define ll long longconst int M = 4e5+10;int tot;int ch[32*M][2],cnt,head[M];int val[32*M],a[M],pre[M],nex[M],dp[M],ans;struct node{ int to,next; ll w;}e[M*2];void add(int u,int v,int w){ e[++cnt].to = v;e[cnt].w = w;e[cnt].next = head[u];head[u] = cnt;}void init(){ tot = 1; ans = 0; cnt = 0; ch[0][0] = ch[0][1] = 0; memset(head,0,sizeof(head));}void ins(ll x){ int u = 0; for(int i = 31;i >= 0;i --){ int v = (x>>i)&1; if(!ch[u][v]){ ch[tot][0] = ch[tot][1] = 0; val[tot] = 0; ch[u][v] = tot++; } u = ch[u][v]; } val[u] = x;}int query(int x){ int u = 0; for(int i = 31;i >= 0;i --){ int v = (x>>i)&1; if(ch[u][v^1]) u = ch[u][v^1]; else u = ch[u][v]; } return x^val[u];}void dfs(int u,int fa,int val){ ins(val); for(int i = head[u];i;i = e[i].next){ int v = e[i].to; if(v == fa) continue; ans = max(ans,query(val^e[i].w)); dfs(v,u,val^e[i].w); }}int main(){ int n,u,v,w; while(scanf("%d",&n)!=EOF){ init(); for(int i = 1;i < n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(0,-1,0); printf("%d\n",ans); }}

 

转载于:https://www.cnblogs.com/kls123/p/10724745.html

你可能感兴趣的文章
VM VirtualBox安装Centos6.5
查看>>
C复习篇 - 使用Posix标准线程库 Porgramming with Pthread
查看>>
socket 通讯 端口绑定 问题 解答
查看>>
关于用户需求的调查
查看>>
云计算时代对传统软件工程的冲击
查看>>
Mahout--(三)相似性度量
查看>>
CodeForces 980 C Posterized
查看>>
C#泛型列表List<T>基本用法总结
查看>>
Drug side effect extraction from clinical narratives of psychiatry and psychology patients
查看>>
linux定时备份mysql并同步到其它服务器
查看>>
浅谈分布式事务
查看>>
Spring MVC专题
查看>>
linux grep命令详解(转)
查看>>
Java下获取可用CPU数
查看>>
JAVA学习笔记
查看>>
可编程硬件Arduino初探(1)-开发环境搭建
查看>>
Django静态文件配置
查看>>
关于C#中怎样实现点ENTER键就相当于按下确认输出按钮
查看>>
jqGrid 是一个用来显示网格数据的jQuery插件
查看>>
windows 下 gcc/g++ 的安装
查看>>