| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 5453 | Accepted: 1190 |
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.
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
Sample Input
4 0 1 3 1 2 4 1 3 6
Sample Output
7
Hint
The xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)
这道题要求最长的异或路径：就是在树中找两个节点，两个节点间有唯一路径（因为是树），把路径不断做异或，异或完后求最大的。数据是10万，O（n2）算法超时
题目描述：
给你一棵树，n个节点（n = 100000），n-1条边每条边i都有一个权值wi。
定义任意两点间的权值为：
这两点间的路径上的所有边的值的异或。
比如a点和b点间有i，j，k三条边，那么ab两点间的权值为：wi^wj^wk
求这个最大的权值。
/*基本思路：1.因为有（x^z)^(y^z)==x^y,s所以为了求树上任意两点间的x^y的和，我们可以把从根节点开始到每个点的^值存下来（dfs解决，复杂度 O（n）），然后问题就转变为了从这些数中取出两个数字，使他们的异或值最大 如何在剩下的值中寻找两个数的异或和最大，朴素算法n^2，明显是超时的，---经典解决方法：trie树，边建树的同时边搜索匹配，因为是借助trie比较，复杂度就变为了O(nlogn)，就可以过了*/ #include<iostream> using namespace std; #include<cstdio> #include<cstring> #define N 100010 struct Edge{/*边表*/ int v,w,last; }edge[4*N]; int head[N]={0},t=0; struct Trie{ int next[2]; }trie[N<<4];/*trie树*/ bool visit[N]={false}; int n,ans=0; int value[N]={0},topt=0;/*value数组各结点到结点0的异或长度*/ void add_edge(int u,int v,int w) { ++t; edge[t].v=v; edge[t].w=w; edge[t].last=head[u]; head[u]=t; } void dfs(int k,int val) { visit[k]=true; value[k]=val;/*dfs求value数组的过程*/ for(int l=head[k];l;l=edge[l].last) { if(!visit[edge[l].v]) dfs(edge[l].v,val^edge[l].w); } } void add_trie(int num) { int now=0;/*建trie树的过程*/ for(int i=30;i>=0;--i) { int a=num&(1<<i)?1:0;/*取出num的二进制位的快速方法，注意这里最好用三目运算符解决，我直接用a=num&(1<<i)，虽然结果正确，但是在网上提交总是runtime error*/ if(!trie[now].next[a]) trie[now].next[a]=++topt; now=trie[now].next[a]; } } int find(int num)/*从二进制的第31位到第1位查找最大异或值*/ { int w=0; int now=0; for(int i=30;i>=0;--i) { int a=(num&(1<<i))?0:1;/*获取num的二进制数的第i+1位上的数字的非，这样取出异或值才是最大*/ if(trie[now].next[a]) { w|=(1<<i); now=trie[now].next[a]; } else now=trie[now].next[!a]; } return w; } int main() { while(scanf("%d",&n)==1) { int u,v,w; for(int i=1;i<n;++i) { scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w);/*对于每个无向图中，每个节点只走一次，不能只建一条有向边，而是应该建两条边，给每一个节点做一个visit数组即可*/ add_edge(v,u,w); } dfs(0,0); for(int i=0;i<=n-1;++i) { add_trie(value[i]);/*一边建树*/ int w=0; w=find(value[i]);/*一边查询*/ ans=max(w,ans); } printf("%d ",ans); memset(head,0,sizeof(head));/*对于有多组测试数据的题目，不要忘记每次循环，把所有的量都初始化*/ memset(value,0,sizeof(value)); memset(trie,0,sizeof(trie)); memset(edge,0,sizeof(edge)); memset(visit,0,sizeof(visit)); topt=0;t=0;ans=0;n=0; } return 0; }