这题是51nod上一个题目稍微变形了一下：完全图最小生成树
原题是 对于一个完全图 每条边（u,v）的边权都是 a[u]^a[v] 求一个最小生成树
但是如果暴力去做的话 肯定会爆时间 n=1e5 边数就是n的平方级别的 我们需要去优化建立生成树的过程
有一个明显的想法是 从最高位开始 我们把当前位为0的分成一块 为1的分成一块 那么肯定是所有为1的在一个联通块内 所有为0的在一个联通块内 因为这样的话 为1的联通块的边权会尽量小 为0的联通块也是
那么要连接这两个联通块 就需要在他们之间 建立一条边 显然我们可以先把 为0的联通块的点权放入trie 然后再遍历为1的联通块的点权 得到一个最小异或值 即可
这样的话我们可以得到一个分治思路 从最高位开始 每次分成01 两块 在这两块中建立最小边权 在递归解决两个子问题即可 然后这道题还需要计数 计数的话有个公式 完全图的生成树个数为 ： n^(n-2) 种
不过牛客的题没有计数 会简便很多 每次加上最小边权就可以了
复杂度是 n(logn^2) 的
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int h[N],nex[N<<1],to[N<<1],edge[N<<1];
int trie[N*32][2],tot,a[N],n,s[N],t[N],cur;
const int inf=(1<<30);
typedef long long ll;
ll sum;
inline int in(){int x=0;char c=0;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}
void add_edge(int x,int y,int z){to[++cur]=y;nex[cur]=h[x];edge[cur]=z;h[x]=cur;
}
void dfs(int u,int f){for(int i = h[u]; i; i = nex[i]){int v = to[i];if(v==f) continue;a[v]=a[u]^edge[i];dfs(v,u);}
}
void init(){for(int i = 0; i <= tot; i++) trie[i][0]=trie[i][1]=0;tot=0;
}
void ins(int x){int p=0;for(int i = 29; i >= 0; i--){int c=(x>>i)&1;if(!trie[p][c]) trie[p][c]=++tot;p=trie[p][c];}
}
inline int getmi(int x){int ans=0,p=0;for(int i = 29; i >= 0; i--){int c = (x>>i)&1;if(trie[p][c]) ans|=c<<i,p=trie[p][c];else ans|=(c^1)<<i,p=trie[p][c^1];}return (ans^x);
}
void solve(int st,int ed,int now){if(st>=ed) return;if(now<0) return;int cnt1=0,cnt2=0;for(int i = st; i <= ed; i++)if((a[i]>>now)&1) s[++cnt1]=a[i];else t[++cnt2]=a[i];for(int i = 1; i <= cnt1; i++) a[i+st-1]=s[i];for(int i = 1; i <= cnt2; i++) a[st+cnt1+i-1]=t[i];init();for(int i = 1; i <= cnt2; i++) ins(t[i]);int mi=inf;if(cnt2){for(int i = 1; i <= cnt1; i++){int k=getmi(s[i]);mi=min(mi,k);}}if(mi!=inf) sum+=mi;solve(st,st+cnt1-1,now-1);solve(st+cnt1,ed,now-1);
}
int main(){n=in();for(int i = 1; i < n; i++){int u,v,w;u=in(),v=in(),w=in();u++,v++;add_edge(u,v,w);add_edge(v,u,w);}dfs(1,0);solve(1,n,29);printf("%lld\n",sum);return 0;
}