P4551最长异或路径

链接

luogu

思路

从\(1\)开始\(dfs\)求出\(xor\)路径。然后根据性质\(x\)到\(y\)的\(xor\)路径就是\(xo[x]^xo[y]\)

代码

#include <bits/stdc++.h> using namespace std; const int _=1e5+7; int xo[_],w[_],ans=-1,num=0; struct node { int v,q,nxt; }e[_<<1]; int head[_],tot; void add(int u,int v,int q) { e[++tot].v=v; e[tot].q=q; e[tot].nxt=head[u]; head[u]=tot; } int ch[_*30][2],cnt; void insert(int x,int ad) { int p=0; for(int i=30;i>=0;--i) { bool k=x&(1<<i); if(!ch[p][k]) ch[p][k]=++cnt; p=ch[p][k]; } } void query(int x) { int tmp=0,p=0; for(int i=30;i>=0;--i) { bool k=x&(1<<i); if(ch[p][!k]) p=ch[p][!k],tmp|=1<<i; else p=ch[p][k]; } ans=max(ans,tmp); } void dfs(int u,int fa) { insert(xo[u],1); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa) continue; xo[v]=xo[u]^e[i].q; dfs(v,u); } } int main() { int n,u,v,q; scanf("%d",&n); for(int i=1;i<n;++i) { scanf("%d%d%d",&u,&v,&q); add(u,v,q),add(v,u,q); } dfs(1,0); for(int i=1;i<=n;++i) query(xo[i]); printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/dsrdsr/p/11405999.html

相关资源：JAVA上百实例源码以及开源项目