传送门 首先假设1为根，求出根到当前节点的xor距离。 然后将xor距离转化为二进制串，建立Trie树。 强制一些点在答案上，然后在Trie树上跑贪心。 显然答案是正确的。 时间复杂度O（n*32）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> #define N 100005 using namespace std; struct edge{int to,next,v;}e[N*2]; int head[N],d[N],a[N][32],c[N*32][2],bin[32]; int n,x,y,z,tot,cnt,ans,top,sum; void add(int x,int y,int v){ e[++tot]=(edge){y,head[x],v}; head[x]=tot; } void dfs(int x,int fa,int v){ d[x]=v; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa) dfs(e[i].to,x,v^e[i].v); } int main(){ scanf("%d",&n); for (int i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } dfs(1,-1,0); cnt=1; ans=0; for (int i=bin[0]=1;i<=30;i++) bin[i]=bin[i-1]*2; for (int i=1;i<=n;i++){ x=1; top=0; for (;d[i];d[i]/=2,top++) a[i][top]=d[i]%2; for (int j=30;j>=0;j--){ if (!c[x][a[i][j]]) c[x][a[i][j]]=++cnt; x=c[x][a[i][j]]; } } for (int i=1;i<=n;i++){ sum=0,x=1; for (int j=30;j>=0;j--){ if (c[x][a[i][j]^1]!=0) sum+=bin[j],x=c[x][a[i][j]^1]; else x=c[x][a[i][j]]; } ans=max(ans,sum); } printf("%d",ans); }