题目链接：点击查看
题目大意：给出一棵树，每条边上都有一个边权，现在问能否选择两个点，使得其间路径上的异或和最大
题目分析：直接求肯定是比较复杂的，我们可以转换一下题意，因为是一棵树，所以n个点肯定互相都连通且无环，我们可以随便找一个节点当做根节点，跑一遍图的遍历，顺便记录一下根节点到每个点的路径上的异或值，我们用数组d来储存，接下来我们若想求两个点之间的路径异或，就可以直接用d[i]^d[j]来求了，转换成了任意两点之间异或最大的问题的，这个经典问题如果n*n的话可以跑出答案，但必定超时，所以我们可以用字典树来优化，因为给出的权值最大只有，所以我们将其用二进制来表示，建立一棵01字典树，剩下的就是模板题了，为后面的可持久化字典树做准备：
注意，这个题对时间卡的有点死，用vector当邻接表的话会T，只能手写邻接表了
代码：
#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int N=1e5+100; int trie[N*32][2]; int d[N]; int head[N]; int cnt,tot; struct Node { int to,w,next; }edge[N*2]; void addedge(int u,int v,int w) { edge[tot].to=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; edge[tot].to=u; edge[tot].w=w; edge[tot].next=head[v]; head[v]=tot++; } int newnode()//动态初始化 { cnt++; trie[cnt][0]=trie[cnt][1]=0; return cnt; } void insert(int x) { int pos=0; for(int i=31;i>=0;i--) { int to=(x>>i)&1; if(!trie[pos][to]) trie[pos][to]=newnode(); pos=trie[pos][to]; } } int search(int x) { int pos=0; int ans=0; for(int i=31;i>=0;i--) { int to=(x>>i)&1; if(trie[pos][!to]) { pos=trie[pos][!to]; ans|=(1<<i); } else pos=trie[pos][to]; } return ans; } void dfs(int u,int fa,int k) { d[u]=k; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; int w=edge[i].w; if(v==fa) continue; dfs(v,u,k^w); } } void init() { memset(head,-1,sizeof(head)); trie[0][1]=trie[0][0]=0;//记得给根节点清零 tot=cnt=0; } int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false); int n; while(scanf("%d",&n)!=EOF) { init(); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); u++,v++; addedge(u,v,w); } dfs(1,-1,0); for(int i=1;i<=n;i++) insert(d[i]); int ans=0; for(int i=1;i<=n;i++) ans=max(ans,search(d[i])); printf("%d\n",ans); } return 0; }
