首页 > 代码库 > The xor-longest Path
The xor-longest Path
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 3875 | Accepted: 850 |
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
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)
這道題由於沒看到多組數據，WA了很久，題目比較簡單，但是運用了a xor b= a xor c xor b xor c，這應該是解異或題目常用的技巧。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>#include<stack>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 110000#define MAXV MAXN#define MAXE MAXV*2#define MAXT MAXN*200//ACtypedef long long qword;int n,m;struct trie{ int ch[2];}tree[MAXT];int toptr=1;inline void new_node(int &now){ now=++toptr; tree[now].ch[0]=tree[now].ch[1]=0;}int dbg=0;void build_trie(qword x){ dbg++; int now=1; int i; for (i=32;i>=0;i--) { if (!tree[now].ch[(x&(1ll<<i))!=0]) { new_node(tree[now].ch[(x&(1ll<<i))!=0]); } now=tree[now].ch[(x&(1ll<<i))!=0]; } if (dbg==175672) dbg--;}struct Edge{ int np; qword val; Edge *next;}E[MAXE],*V[MAXV];int tope=-1;void addedge(int x,int y,qword z){ E[++tope].np=y; E[tope].val=z; E[tope].next=V[x]; V[x]=&E[tope];}int fa[MAXN],depth[MAXN],val[MAXN];void dfs(int now,int v){ Edge *ne; build_trie(v); val[now]=v; for (ne=V[now];ne;ne=ne->next) { if (ne->np==fa[now])continue; fa[ne->np]=now; dfs(ne->np,v^ne->val); }}qword find(qword x){ int now=1; int ret=0; int i; for (i=32;i>=0;i--) { if (tree[now].ch[(x&(1ll<<i))==0]) { now=tree[now].ch[(x&(1ll<<i))==0]; ret+=1ll<<i; }else { now=tree[now].ch[(x&(1ll<<i))!=0]; } } if (!now)throw 1; return ret;}int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int i,j,k; qword x,y,z; while (~scanf("%d",&n)) { memset(V,0,sizeof(V)); memset(fa,-1,sizeof(fa)); toptr=1; tope=-1; tree[1].ch[0]=tree[1].ch[1]=0; for (i=1;i<n;i++) { scanf(LL LL LL,&x,&y,&z); addedge(x,y,z); addedge(y,x,z); } fa[0]=0; dfs(0,0); qword ans=0; for (i=0;i<n;i++) { ans=max(ans,find(val[i])); } printf(LL "\n",ans); } return 0;}
The xor-longest Path