1 操作相当于有一个年龄为 0 的人已经预先在传销组织里了。
顺序非常难搞。可以看成每个人第一次连边没有贡献。这启发我们把边权直接设为 (也是 ,最后算边权-点权。于是变为一个最大生成树问题。
显然可以 kruskal,枚举边权,枚举以它为权的所有边(边权的子集)。复杂度 。你可能会很惊讶, 是怎么草过这题的呢,小编也很惊讶,但是事实就是这样。
考虑 Boruvka 算法。我们需要做 次以下操作:
考虑如何找点 的最大出边。这里有一个很妙的操作:另一个端点一定是 的子集,如果 中权值最大的点和 不在一个连通块,那么直接取它即可;否则再求一个 和最大值不在一个联通块的最大点。子集DP即可。
代码如下:
xxxxxxxxxx
using namespace std;
const int maxN=262144;
int N;
int A[maxN],fa[maxN];
int find(int x){return (fa[x]==x)?x:fa[x]=find(fa[x]);}
struct node{
int p,c;
node(int p0=-1,int c0=-1){p=p0;c=c0;}
bool operator <(const node b)const{
return p<b.p;
}
bool operator >(const node b)const{
return p>b.p;
}
operator bool(){return p!=-1;}
};
node F[maxN][2];
node maxE[maxN];
int ANS;
signed main(){
scanf("%d",&N);
for(int i=0;i<N;i++) scanf("%d",&A[i]),ANS-=A[i];A[N++]=0;
for(int i=0;i<N;i++) fa[i]=i;
int cnt=N;
while(cnt!=1){
for(int s=0;s<(1<<18);s++)
F[s][0]=F[s][1]=node();
for(int i=0;i<N;i++){
node tmp(A[i],find(i));
if(tmp>F[A[i]][0]){
if(F[A[i]][0].c!=tmp.c) F[A[i]][1]=F[A[i]][0];
F[A[i]][0]=tmp;
}
if(tmp>F[A[i]][1]&&tmp.c!=F[A[i]][0].c) F[A[i]][1]=tmp;
}
for(int i=0;i<18;i++)
for(int s=0;s<(1<<18);s++) if((s>>i)&1)
for(int d=0,t=s^(1<<i);d<2;d++){
node tmp=F[t][d];
if(tmp>F[s][0]){
if(F[s][0].c!=tmp.c) F[s][1]=F[s][0];
F[s][0]=tmp;
}
if(tmp>F[s][1]&&tmp.c!=F[s][0].c) F[s][1]=tmp;
}
for(int i=0;i<N;i++) maxE[i]=node();
for(int i=0;i<N;i++){
int s=((1<<18)-1)^A[i],c=find(i);
if(F[s][0])if(F[s][0].c!=c)
{if(node(A[i]+F[s][0].p,F[s][0].c)>maxE[c]) maxE[c]=node(A[i]+F[s][0].p,F[s][0].c);}
else if(F[s][1])
{if(node(A[i]+F[s][1].p,F[s][1].c)>maxE[c]) maxE[c]=node(A[i]+F[s][1].p,F[s][1].c);}
}
for(int u=0;u<N;u++) if(u==find(u)){
int v=maxE[u].c;
if(find(u)==find(v)) continue;
cnt--;fa[find(u)]=find(v);ANS+=maxE[u].p;
}
}
printf("%lld\n",ANS);
}