点击打开链接
题意，一颗n个结点的树，n<=1e5,每个边有个值，在树上找一条简单路径，使得这条路径上的边权异或值最大
类似于:只要把1~i-1异或前缀插入到Trie中,即可查询到i结尾的最大异或
求出d[u]=root->u的异或值 则u->v路径的异或=d[u]^d[v] 把所有d[i]插入到Trie中,在Trie中查询某个d[u]得到的最大值即为从u出发的最大异或值
坑:这题用vector就TLE..
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; typedef long long ll; const int N=2e5+20; struct Edge{ int v,next,c; }e[N*2]; int n,sz,tot,head[N*2]; int ch[32*N][2],v[32*N],ans; int d[N];//root->u的XOR值 void add_edge(int a,int b,int c) { e[tot]=(Edge){b,head[a],c}; head[a]=tot++; } void init() { memset(ch[0],0,sizeof(ch[0])); memset(v,0,sizeof(v)); sz=1; memset(head,-1,sizeof(head)); tot=0; } void insert(ll x) { int u=0; for(int i=30;i>=0;i--) { int c=(x>>i)&1; if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); ch[u][c]=sz++; } u=ch[u][c]; } v[u]=x; } void dfs(int u,int fa) { for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].v,w=e[i].c; if(v!=fa) { d[v]=d[u]^w; insert(d[v]); dfs(v,u); } } } int query(int x) { int u=0; for(int i=30;i>=0;i--) { int c=(x>>i)&1; if(ch[u][c^1]) u=ch[u][c^1]; else u=ch[u][c]; } return v[u]^x; } int main() { while(scanf("%d",&n)!=EOF) { init(); ans=0; int u,v,w; for(int i=1;i<=n-1;i++) { scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,w); } d[0]=0; insert(0); dfs(0,-1); for(int i=0;i<n;i++) ans=max(ans,query(d[i])); printf("%d\n",ans); } return 0; }
