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?
InputThe 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 uand v of length w.
Output For each test case output the xor-length of the xor-longest path. Sample Input 4 0 1 3 1 2 4 1 3 6 Sample Output 7 HintThe xor-longest path is 0->1->2, which has length 7 (=3 ⊕ 4)
把点到根的值都加到树上求一遍最大异或就行
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; int tot,sz; int si; struct Edge { int v, w,next; }e[200010]; int head[200010]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int nxt[100010*31][2]; int ans; int a[100020]; void insert(int x) { int p=0; for(int i=30;i>=0;i--) { int dd=(x>>i)&1; if(!nxt[p][dd]) nxt[p][dd]=++sz,memset(nxt[sz],0,sizeof(nxt[sz])); p=nxt[p][dd]; } } int ask(int x){ int p=0; int res=0; for(int i=30;i>=0;i--) { int dd=(x>>i)&1; if(nxt[p][1-dd]) p=nxt[p][1-dd],res+=(1<<i); else p=nxt[p][dd]; } return res; } void dfs(int u,int fa,int now) { a[++tot]=now; for(int i=head[u];~i;i=e[i].next) { if(e[i].v==fa) continue; dfs(e[i].v,u,(now^e[i].w)); } } void add(int u,int v,int w) { e[si].v=v,e[si].next=head[u];e[si].w=w;head[u]=si++; } int main() { int n; while(~scanf("%d",&n)) { tot=0,sz=0; si=1; memset(head,-1,sizeof(head)); memset(nxt[0],0,sizeof(nxt[0])); ans=0; for(int i=1;i<n;i++) { int u,v,w; u=read(),v=read(),w=read(); add(u,v,w); add(v,u,w); } dfs(0,-1,0); for(int i=1;i<=tot;i++) { ans=max(ans,ask(a[i])); insert(a[i]); } printf("%d\n",ans ); } }
