CF1446C Xor Tree

对于每个点i，找到j≠i且a_j xor a_i最小，连边(i,j)。

如果连边之后形成一棵树，那么称{a_i}为合法的。

给出{a_i}，求至少删掉多少个点才合法。

n≤2∗10^5

a_i互不相同

考虑到序列中 n 个点产生的 n 条边，必然有重合的两条边（异或值最小的点对产生的两条边），故一个序列不可能连接成一个简单环（最多有 n-1 条边），那么就考虑怎么删除最少的点能够把连通块合并。

考虑将每个数字插入 01Trie

显然，每个点会和一个和最近的一个点连边（因为每个点深度一样，在 01Trie 上，最近的点一定是和这个点异或值最小的点）

在 Trie 上，找一点 X 与某点 Y ，使它们的 BIT 位拥有最长公共前缀，那么 X 即为 Y 距离最近的点

因为它们的 BIT 位拥有最长公共前缀，所以在所有的点中 X ，与 Y 的异或值最小。

那么如果某个节点的两个儿子的大小都大于 2，就说明两个儿子的内部各自形成了连通块

那么必须把一个子树的点删成仅剩1个节点，才能与另一个儿子合并成一个连通块。

直接在最小的子树保留一个点，其他的都删了就好，直接一遍dfs

#include<bits/stdc++.h>
const int N = 1e7+10;
int trie[N][2],rt=1,cnt=1;
int end[N],size[N];
int a[N],n;
int b[40],ans;
void insert(){
    int nw=rt;
    for(int i=1;i<=31;++i){
        if(!trie[nw][b[i]])
            trie[nw][b[i]]=++cnt;
        nw=trie[nw][b[i]];
    }
    end[nw]++;
}
void dfs(int x){
    size[x]=end[x];
    if(end[x]) return ;
    for(int i=0;i<=1;++i){
        if(trie[x][i])
            dfs(trie[x][i]);
        size[x]+=size[trie[x][i]];
    }
    //printf("%d %d\n",x,size[x]);
    if(size[trie[x][0]]>=2&&size[trie[x][1]]>=2){
        ans+=std::min(size[trie[x][0]]-1,size[trie[x][1]]-1);
        size[x]=std::max(size[trie[x][0]],size[trie[x][1]])+1;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        for(int j=1;j<=31;++j){
            b[31-j+1]=a[i]&1;
            a[i]>>=1;
        }
        insert();
    }
    dfs(rt);
    printf("%d",ans);
    return 0;
}