题目描述
给出一课n个节点的带权树，求树上最长异或路径。
思路
这道题其实思路和Nikitosh 和异或差不多，都是利用异或的性质转化，再用字典树维护。首先我们知道树上两点必定有且只有一条简单路径，并且他们的关系有两种情况：①他们具有祖孙关系，对于这种情况，我们记f[i]表示根节点到i的异或路径，那么f[i]^f[j]即为i、j的异或路径；②他们不具有祖孙关系，那么我们假如已知他们的LCA，，根据第一种情况，所以异或路径值为（f[i]^f[lca]）^（f[lca]^[j]），而异或操作满足交换律和结合律，因此即为f[i]^f[j]。我们已经得出了树上两点间的异或路径的求法。只有处理出f数组，题目就相当于从f数组中选出两个数使它们的异或值最大，有字典树即可。
代码
#include <bits/stdc++.h> using namespace std; const int MAXN=2e5+10; int ch[1010005][3],f[MAXN]; int nxt[MAXN<<1],head[MAXN],to[MAXN<<1],w[MAXN],tot; void add_edge(int x,int y,int z) { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; w[tot]=z; } void dfs(int u,int fa) { for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(v==fa)continue ; f[v]=f[u]^w[i]; // cout<<v<<' '<<f[v]<<endl; dfs(v,u); } } void insert(int x) { int u=1; for(int i=1<<30;i;i>>=1) { int num=(x&i)?1:0; if(!ch[u][num])ch[u][num]=++tot; u=ch[u][num]; } } int find(int x) { int u=1,ans=0; for(int i=1<<30;i;i>>=1) { int num=(x&i)?0:1; if(ch[u][num]) { u=ch[u][num]; ans+=i; } else u=ch[u][!num]; } return ans; } int main() { int n; scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,w); } dfs(1,0); tot=1; // for(int i=1;i<=n;i++) // printf("%d ",f[i]); // printf("\n"); for(int i=1;i<=n;i++) insert(f[i]); int ans=0; for(int i=1;i<=n;i++) ans=max(ans,find(f[i])); printf("%d",ans); return 0; }