题意

给定 个数 ，若 则 有边，现在你要将图连成有根森林，定义 的贡献为 乘它的儿子数，求贡献总和最大值。

思路

考虑这么一件事情， 乘以儿子数可以变为 的度数减去一个 （根节点除外）。

然后既然每个点都要减一次，那么这部分贡献可以直接提出来不管。

接下来考虑根节点除外非常不优雅，考虑我们人为造一个好的根，我们发现加一个 ，这样就一定可以连成树，而且根节点的贡献就不用管了。

于是问题转化成了对于 ，它们之间有权值为 的边，然后跑最大生成树。

你发现 ，所以可以直接用 kruskal 的方法枚举边权，然后跑子集卷积，复杂度最优可以为 ，注意这里并查集的复杂度是不乘到子集卷积的部分里的，因为查询不增加势能。

CODE

#include<cstdio>
using namespace std;
using ll=long long;
const int N=400010,FSIZE=1<<26;
int n,s[N];
ll ans,sum[N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
int root(int x){return(s[x]!=x?s[x]=root(s[x]):x);}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=sum[0]=1,x;i<=n;++i){
        read(x);ans-=x;++sum[s[x]=x];
    }
    for(int i=N-1;i;--i)
        for(int j=i,x,y;j>(i^j);--j&=i)
            if(sum[j]&&sum[i^j]&&(x=root(j))!=(y=root(i^j))){
                ans+=i*(sum[j]+sum[s[x]=y]-1);
                sum[j]=sum[i^j]=1;
            }
    printf("%lld\n",ans);
    return(0);
}