对于每个点(i)，找到(j eq i)且(a_j xor a_i)最小，连边((i,j))。
如果连边之后形成一棵树，那么称({a_i})为合法的。
给出({a_i})，求至少删掉多少个点才合法。
(nle 2*10^5)
(a_i)互不相同
这题搞得可真是惊心动魄……搞了三个做法，最后一个终于对了……
干了1.5h。
假设连有向边(i o j)，那么建出的图是个基环树森林。并且每棵基环树的环长为(2)。
如果合法，那么必须满足：只存在一对((i,j))，满足对于各自而言，(a_i xor a_j)都是最小的。
自然这也会是全局最小异或值。之前有个结论，对于一堆朴素的({a_i})，其中最小的(a_i xor a_j)一定是排序之后相邻的。
于是最终如何保留树才合法呢？建出Trie，发现长这样：
这样dfs找一下就好了。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200005
#define INF (1<<30)
int n;
int a[N];
struct Node{
Node *c[2];
int siz;
} d[N*40],*rt;
int cnt;
void insert(int x,int c=1){
Node *t=rt;
for (int i=29;i>=0;--i){
t->siz+=c;
if (!t->c[x>>i&1]){
t->c[x>>i&1]=&d[++cnt];
d[cnt]={NULL,NULL};
}
t=t->c[x>>i&1];
}
t->siz+=c;
}
int ans;
void dfs(Node *t,int s){
if (t->c[0] && t->c[0]->siz==1 && t->c[1] && t->c[1]->siz==1)
ans=max(ans,2+s);
if (t->c[0]) dfs(t->c[0],s+(t->c[1]?1:0));
if (t->c[1]) dfs(t->c[1],s+(t->c[0]?1:0));
}
int main(){
// freopen("in.txt","r",stdin);
rt=&d[cnt=1];
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%d",&a[i]);
insert(a[i]);
}
ans=2;
dfs(rt,0);
printf("%d
",n-ans);
return 0;
}