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;
}