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;
}
0 条评论