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,原来每个有根树的根设为这个点的儿子。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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
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;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×