题目链接
题意：n个点的完全图，每个点有一个点权，在i和j之间连一条边的代价是Ai^Aj 求最小生成树的权值，n<=2e5，Ai<2^30
题解：考虑这么一种求mst的方法，每次将当前点集分为两部分S，T，分别递归到S,T做，再找一条连接S，T的权值最小的边把两个集合合并起来。我们按位从大到小处理，每次根据这一位是0还是1分成两个集合，找两个集合间的最小边可以用trie解决，复杂度O(nlog*30)。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int MaxN=2e5+5; int N,Tot; int A[MaxN],Son[MaxN*30][2]; void Insert(int x){ int i,u=0,c; for(i=29;~i;i--){ c=(x>>i&1); if(!Son[u][c]) Son[u][c]=++Tot; u=Son[u][c]; } } int Get_Mn(int x){ int i,u=0,mn=0,c; for(i=29;~i;i--){ c=(x>>i&1); if(Son[u][c]) u=Son[u][c]; else mn+=(1<<i),u=Son[u][c^1]; } return mn; } LL Solve(int now,int d,int l,int r){ if(d<0||l==r) return 0; if(A[r]<now+(1<<d)) return Solve(now,d-1,l,r); if(A[l]>=now+(1<<d)) return Solve(now+(1<<d),d-1,l,r); int i,j,pos=lower_bound(A+l,A+r+1,now+(1<<d))-A-1,mn=1<<30; for(i=pos+1;i<=r;i++) Insert(A[i]); for(i=l;i<=pos;i++) mn=min(mn,Get_Mn(A[i])); for(i=0;i<=Tot;i++) Son[i][0]=Son[i][1]=0; Tot=0; return mn+Solve(now,d-1,l,pos)+Solve(now+(1<<d),d-1,pos+1,r); } int main(){ freopen("888G.in","r",stdin); freopen("888G.out","w",stdout); int i; scanf("%d",&N); for(i=1;i<=N;i++) scanf("%d",&A[i]); sort(A+1,A+N+1); printf("%I64d\n",Solve(0,29,1,N)); return 0; }