[POJ 3764] The xor-longest Path （Tire树 + 贪心）

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

POJ - 3674
题意是给你一个树，每条边有一个权值，求得树上一条路径，使路径上每条边权值的异或和最大
首先用一个 DFS把根到任意点的路径的异或和求出来 xorv[i]
由异或的性质可得点 u和点 v的异或和即为 xorv[u]^xorv[v] （根到两点 LCA的异或和会消去）
然后问题就转化成在区间内找两个值，使得他们的异或和最大
与 LightOJ - 1269一样的做法，用 trie树维护一下，贪心找最大就好
http://blog.csdn.net/u012015746/article/details/51089181

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}const int maxn=1e5+10,noden=maxn*31+10;
struct trnode
{int now,nxt[2];
};
int N;
int edge[2*maxn][4];
int last[maxn];
int xorv[maxn];
int trien;
trnode trie[noden];void adde(int,int,int,int);
int dfs(int,int);
void insert(int);
int findmax(int);int main()
{while(~scanf("%d", &N)){trien=0;CLR(last);CLR(xorv);CLR(trie);for(int i=1; i<N; i++){int u,v,w;scanf("%d%d%d", &u, &v, &w);adde(u,v,w,i);adde(v,u,w,i+N);}dfs(0,-1);int tmax=0;for(int i=0; i<N; i++){tmax=maxx(tmax, findmax(xorv[i]));insert(xorv[i]);}printf("%d\n", tmax);}return 0;
}void adde(int u, int v, int w, int i)
{edge[i][0]=u;edge[i][1]=v;edge[i][2]=w;edge[i][3]=last[u];last[u]=i;
}int dfs(int u, int f)
{for(int e=last[u]; e; e=edge[e][3]){int v=edge[e][1],w=edge[e][2];if(v==f) continue;xorv[v]=w^xorv[u];dfs(v,u);}
}void insert(int num)
{int np=0;for(int i=31; i>=0; i--){int now=(num&(1<<i))?1:0;if(trie[np].nxt[now]){np=trie[np].nxt[now];}else{trie[np].nxt[now]=++trien;np=trien;trie[np].now=now;}}
}int findmax(int num)
{int np=0;for(int i=31; i>=0; i--){int now=(num&(1<<i))?1:0;if(trie[np].nxt[now^1]) np=trie[np].nxt[now^1];else if(trie[np].nxt[now]) np=trie[np].nxt[now];else break;num^=(trie[np].now)<<i;}return num;
}