零点的钟声敲响，猴年终于到来啦~
在这新年的第一天，猴族首领猴腮雷打算重新规划一下猴族领地的交通。
猴族领地中有 $n$ 个城市，其中第 $i$ 座城市的繁荣度为 $a_i$。猴族领地中任意两个城市之间都可以修建双向道路，在第 $i$ 座城市和第 $j$ 座城市之间修建道路可以给新的一年带来 $a_i \mathbin{\mathrm{and}} a_j$ 的繁荣度。其中 $\mathbin{\mathrm{and}}$ 表示按位与运算，例如 $2 \mathbin{\mathrm{and}} 3 = 2$，$1 \mathbin{\mathrm{and}} 0 = 0$，$1 \mathbin{\mathrm{and}} 1 = 1$。
为了彰显自己的功绩，猴族首领猴腮雷决定修建若干条道路，使得任意两个城市之间都可以只通过他新修建的道路直接或者间接到达，为了发扬节约精神，他决定修建恰好 $n - 1$ 条道路。一个修建方案的繁荣度是所有要修建的道路带来的繁荣程度之和。
作为一个英明的首领，猴腮雷决定在所有可行的方案中选择繁荣度最大的方案，现在他想要知道他选择的方案的繁荣度，但是因为他日理万机，没有时间来想这种简单的小问题，于是他就让你来帮忙啦。
第一行包含两个正整数 $n, m$ ($n \leq 10^5; m \leq 18$)。
第二行包含 $n$ 个非负整数 $a_1, a_2, \cdots, a_n$ ($0 \leq a_i < 2^m$)。
输出一行一个整数，表示所有方案中最大的繁荣度。
先来考虑 $m = 1$ 时怎么做。
此时所有点的权值只有 $0$ 和 $1$，因此整张图中，如果 $e = (u, v)$ 的边权为 $1$，当且仅当 $w_u = w_v = 1$，即它两端的点权均为 $1$。
设图中有 $k$ 个点的权为 $1$，$n - k$ 个点的权为 $0$。则权为 $1$ 的边导出的图是完全图 $K_k$。因此，此时最大生成树的边权和应为 $k - 1$ ($K_k$ 的一个生成树)。
那对于一般的 $m$ 怎么做呢？
其实上面的算法给了一点启发：如果 $u, v$ 的点权相同，设 $w_u = w_v = w$。若 $u, v$ 在最大生成树中没有边相连，则取生成树中 $u - v$ 的一条路径 $u - a - \cdots - v$。则 $\mathrm{dist}(u, a) = w \mathbin{\&} w_a \leq w = w \mathbin{\&} w = \mathrm{dist}(u, v)$，因此可以断开 $(u, a)$ 连接 $(u, v)$ 使总权值不减。
因此接下来可以设 $(u, v) \in T_\max$。这样以来，由于 $w_u = w_v = w$，因此一切与 $v$ 相连的点都可以改接到 $u$ 使得总权值不变。此时 $v$ 就是叶子。因此对于权值相同的节点，每多出现一次就直接与之前的点相连，贡献总权值后删去。
接下来假设所有点的权值不同。
由 Kruskal 算法的思想，求最大生成树，就是边权从大到小添加，形成连通块。
我们从 $2^m - 1$ 到 $0$ 枚举边权，对于一个边权 $f_0$，考虑所有满足点权 $w \sqsubseteq f_0$ 的点 (注：二进制数 $a \sqsubseteq b$ 为将 $a, b$ 理解为集合后的子集关系，即 $a \mathbin{\&} b = a$)。
这些点连成的边就是此时边权最大的边，且边权均为 $f_0$。若还有边权更大的边，则它们已经在之前的几轮中被合并。故此时剩下的点的点权一定为 $f_0 \mid \sum 2^i$ 且 $\sum 2^i$ 部分互不相交。
因此，我们只需将这些点形成的连通块合并起来即可。
实现时，可以用一个数组 $a$ 存储当前边权所在的连通块 (的一个代表点)，合并好之后，将 $a \left[ f_0 \right]$ 置为该连通块中的一个点。
总时间复杂度 $O \left( n + m 2^m \right)$。
#include <bits/stdc++.h>
#define N 100005
#define M 262500
int n, B;
int a[M], p[N];
int ancestor(int x) {return p[x] == x ? x : (p[x] = ancestor(p[x]));}
inline bool test(int x, int y, bool un = false) {
if ((x = ancestor(x)) == (y = ancestor(y))) return true;
if (un) p[x] = y; return false;
}
int main() {
int i, j, v; long long ans = 0;
scanf("%d%d", &n, &B);
for (i = 1; i <= n; ++i) {
p[i] = i; scanf("%d", &v);
a[v] ? ans += v : (a[v] = i);
}
for (i = ~(-1 << B); i; --i) {
int &u = a[i];
for (j = 0; j < B && !u; ++j) u = a[i | 1 << j];
for (; j < B; ++j)
if ((v = a[i | 1 << j]) && !test(u, v, true)) ans += i;
}
printf("%lld\n", ans);
return 0;
}
坑1：注意在连接同一种权值的边时，不要忘记判断该点是否存在，以免对答案重复计算。