POJ 3764 The xor-longest Path

2024-01-11 11:18

文章标签 path poj longest xor 3764

本文主要是介绍POJ 3764 The xor-longest Path，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 3089		Accepted: 681

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

Sample Output

Hint

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

题目分析：

1.采用深搜，很容易就能够计算出任何一个节点n到根节点r的xor-lenngth，放入数组value中.

2.可根据xor的性质，a xor a=0，很容易求得树中任意两个节点n1、n2的xor-length为value[n1] xor value[n2].可从两个方面思考这个问题，1）n1,n2间的路径经过根节点r，这样刚好;2)n1,n2间路径不经过根节点r，这时候他们到根节点的重叠部分正好消掉.（注意这里的数据结构是树，一条路径假若不经过根则n1,n2必定是父子（祖父子）关系）

3.很直白的办法是进行遍历两两匹配，但是肯定可以想象，会超时！这里参考字典树的思想，把n个value插入树中，查找的时候最大值一定是那个最高位与当前value的最高位不同的那个（抑或的性质）

遇到的问题：

虽然采用字典树对速度进行了提升，但是还是tle，最后我把所有输入输出都改成C语言的库函数（以前用的C++对象），居然ac了，顿时感到了伤不起！！！

代码：

#include<iostream>
#include<fstream>
using namespace std;#define M 100010struct node
{int v,next,w;
}edge[M<<1];
struct trie{int next[2];
}t[M<<5];int n,e,tt;
int head[M];
int vis[M];
int value[M];void addEdge(int u,int v,int w)
{edge[e].v=v;edge[e].next=head[u];edge[e].w=w;head[u]=e++;edge[e].v=u;edge[e].next=head[v];edge[e].w=w;head[v]=e++;
}void dfs(int x,int w)
{value[x]=w;vis[x]=1;for(int i=head[x];i;i=edge[i].next){if(vis[edge[i].v]!=1){dfs(edge[i].v,w^edge[i].w);}}
}void insert(int w)
{int i,a,p=0;for(i=30;i>=0;i--){a=w&(1<<i)?1:0;if(!t[p].next[a]){t[p].next[a]=++tt;t[tt].next[0]=0;t[tt].next[1]=0;}p=t[p].next[a];}
}int find(int w)
{int i,a,p=0,max=0;for(i=30;i>=0;i--){a=w&(1<<i)?0:1;if(t[p].next[a]){max|=(1<<i);p=t[p].next[a];}else{p=t[p].next[!a];}}return max;
}int main()
{freopen("data.in","r",stdin);while(cin>>n){for(int i=0;i<n;i++){vis[i]=head[i]=0;}e=1;for(int i=0;i<n-1;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addEdge(u,v,w);}dfs(0,0);t[0].next[0]=0;t[0].next[1]=0;tt=0;int max=0,u;for(int i=0;i<n;i++){insert(value[i]);u=find(value[i]);if(max<u)max=u;}cout<<max<<endl;}return 0;
}

这篇关于POJ 3764 The xor-longest Path的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！