考虑若 \(a_u\operatorname{bitand} a_v = 0\),则连 \((u, v, a_u), (v, u, a_v)\) 两条单向边,答案即为外向森林边权和最大值。
发现这是个森林,那考虑增加一个虚点 \(a_{n + 1} = 0\),这样就变成了一个树,然后能发现 \(1\sim n\) 的每个点的入度肯定都为 \(1\),那就考虑连成 \((u, v, a_u + a_v)\) 的双向边跑一个最大生成树,最后答案减掉 \(1\sim n\) 每个点入度的贡献 \(\sum\limits_{i = 1}^n a_n\) 即可。
考虑用 Kruskal 跑最大生成树,大至小枚举边权 \(w\)。
因为 \(u, v\) 要有边需要满足 \(a_u\operatorname{bitand} a_v = 0\),所以 \(a_u + a_v = a_u\oplus a_v\)。
再枚举 \(w\) 二进制下的的子集 \(s\) 分成 \(s,t = w \oplus s\) 两个数,若 \(c_s, c_{t} > 0\)(\(c_i = \sum\limits_{j = 1}^{n + 1} [a_j = i]\))且 \(s, t\) 本身不连通(并查集维护),则可以在这 \(c_s + c_t\) 个点中连 \(c_s + c_t - 1\) 条边(肯定有方案连边),对答案的贡献即为 \((c_s + c_t - 1)\times w\)。
同时合并 \(s, t\) 的连通块,\(c_s, c_t\leftarrow 1\),因为后面 \(s, t\) 可能还要与其他数连边,但此时肯定就只能连其中的一个点了。
时间复杂度 \(O(3^w\times \alpha(n))\),对于此题 \(w = 18\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: G. Kuroni and Antihype
// Contest: Codeforces - Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!)
// URL: https://codeforces.com/problemset/problem/1305/G
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1 << 18;
int fa[N];
int getfa(int i) {
return fa[i] == i ? i : (fa[i] = getfa(fa[i]));
}
int c[N];
int main() {
int n;
scanf("%d", &n);
long long ans = 0;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
c[x]++, ans -= x;
}
c[0]++;
for (int i = 0; i < N; i++) {
fa[i] = i;
}
for (int i = N - 1; i; i--) {
for (int s = i, t = 0; s >= t; s = (s - 1) & i, t = i ^ s) {
if (c[s] && c[t] && getfa(s) != getfa(t)) {
ans += 1ll * (c[s] + c[t] - 1) * i;
c[s] = 1, c[t] = 1, fa[getfa(s)] = getfa(t);
}
}
}
printf("%lld\n", ans);
return 0;
}