Description

Solution

首先注意到实际上约束关系构成了一棵树

考虑这个排列 \(p\),编号为 \(a[i]\) 的出现了,\(i\) 才可以出现

那么如果连边 \((a[i],i)\),就会构成一棵以 \(0\) 为根的树,每一个点只有一个父亲

否则就不合法

因为要父亲被选入,这个点才能被选入,所以排列 \(p\),相当于是这棵树的一种合法的拓扑序

要求的就是代价最大的一个拓扑序

那么问题就和 \(POJ\,2054\) 一样的做法了,用一个神奇的贪心

每次找出全局的权值最小值,往父亲合并,合并成新节点,权值为平均值,即 \(\frac{\sum w_i}{size}\)

答案加上被合并的点的权值乘以父亲的 \(size\)

正确性感性理解一下,具体证明和国王游戏差不多,发现 \(swap\) 之后不会更优

实现可以用一个堆或者 \(set\) 实现

然而 \(set\) 被卡常了,开 \(O2\) 才能过

#include
    
     using namespace std;typedef long long ll;const int N=1000010;int n,a[N],w[N],head[N],nxt[N],to[N],num=0,in[N],fa[N];inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;}inline bool topsort(){    queue
     
      Q;    Q.push(0);    while(!Q.empty()){        int x=Q.front();Q.pop();        for(int i=head[x];i;i=nxt[i]){            int u=to[i];            if(!(--in[u]))Q.push(u);        }    }    for(int i=1;i<=n;i++)if(in[i]>0)return false;    return true;}struct data{    ll w;int s,x;    bool operator <(const data &p)const{        if(w*p.s!=p.w*s)return w*p.s
      
       Q;int cnt=0,b[N];inline int find(int x){return b[x]==x?x:b[x]=find(b[x]);}int main(){  freopen("perm.in","r",stdin);  freopen("perm.out","w",stdout);  scanf("%d",&n);  for(int i=1;i<=n;i++)        scanf("%d",&a[i]),link(a[i],i),in[i]++,fa[i]=a[i];  for(int i=1;i<=n;i++)scanf("%d",&w[i]);  if(!topsort()){puts("-1");return 0;}  for(int i=1;i<=n;i++){      p[i]=(data){w[i],1,i};      Q.insert(p[i]);b[i]=i;  }  cnt=n;p[0].s=1;  ll ans=0;  data t;  while(!Q.empty()){      t=*Q.begin();Q.erase(t);      int y=find(fa[t.x]);      ans+=t.w*p[y].s;      if(y){          Q.erase(p[y]);          data e=t;          e.w+=p[y].w;e.s+=p[y].s;e.x=++cnt;          b[cnt]=cnt;b[y]=cnt;b[find(t.x)]=cnt;          fa[cnt]=fa[y];fa[t.x]=cnt;          p[cnt]=e;          Q.insert(e);      }      else b[find(t.x)]=0,p[0].s+=t.s;  }  cout<
       
        <