【题解】CF1305G Kuroni and Antihype

CF1305G Kuroni and Antihype

有 $n$ 个人，第 $i$ 个人年龄为 $a_i$，两个人 $i,j$ 是朋友当且仅当 $a_i\ \texttt{ AND }\ a_j=0$。现在这 $n$ 个人要加入传销组织，组织会给他们金币。
主动加入的不会得到金币。
一个人 $i$ 若在组织内，则可以邀请不在组织内的朋友 $j$ 加入，并得到 $a_i$ 的金币。一个人只能被邀请一次。
问 $n$ 个人最多得到多少金币。
$n,a_i\le 2\times 10^5$。

$\texttt{Solution}$

显然所有人都加入最优。

如果两人是朋友，则在两人之间连边。

不难发现，最后取出来的一定是一棵生成树，需要做的是选择一些人作为主动加入的。令 $x,y$ 之间的边的边权为 $x+y$，最后答案就是最大生成树的权值和 $W$ 减去 $\sum_{i=1}^n a_i$，再把那些主动加入的点的权值加回来。

不妨设一个虚点 $i+1$，有 $a_{i+1}=0$。则任一点与 $i+1$ 连边。 这样的话，只要看做让 $i+1$ 主动加入即可。

则跑出最大生成树，权值减去 $\sum_{i=1}^n a_i$ 即可。

如何连边？发现 $a_i$ 不大，考虑放在桶里。两点之间有边，则按位与为 $0$，有 $x+y=x\ \texttt{ xor }\ y$。则考虑从大到小枚举边权 $w$，然后暴力枚举他的子集 $x$ 与其补集 $y$。并查集路径压缩，按秩合并即可。

时间复杂度 $\mathcal{O}(3^{18}\times \alpha(n))$。