CF1305G

link

题解

考虑对于一个有根树，每条$fa_v=u$的边的贡献是$w_u$，也就是$(w_u+w_v)-w_v$，由于除了根每个$v$只有一个$f_v$，则总贡献就是$\sum(w_u+w_v)-\sum w_v+w_r$。

建一个超级根，点权为0，原来每个有根树的根设为这个点的儿子。

那么总贡献就是边权和-点权和。

点权和固定了，边权和可以直接最大生成树算。

int a[1<<18|5];
int dis[1<<18|5],cnt[1<<18|5];
priority_queue<int> pq;
const int m=1<<18;
int fa[1<<18|5];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
ll ans;
void link(int u,int v,int w){
    if(cnt[u] && cnt[v]){
        u=find(u);v=find(v);    
        if(u!=v){
            ans+=(ll)w*(cnt[u]+cnt[v]-1);fa[u]=v;cnt[v]=1;
        }
    }
}
signed main(){
#ifdef QAQAutoMaton 
    freopen("G.in","r",stdin);
    freopen("G.out","w",stdout);
#endif
    int n;
    read(n);
    int x;
    for(int i=1;i<=n;++i){
        read(x);
        ++cnt[x];
        ans-=x;
    }
    cnt[m]=1;
    fa[m]=m;
    for(int i=0;i<m;++i){
        fa[i]=i;
    }
    for(int i=m-1;~i;--i){
        for(int j=i;;j=(j-1)&i){
            link(j,i^j,i);    
            if(!j)break;
        }
        link(i,m,i);
    }
    write(ans,'\n');
    return 0;
}