【HNOI2018】排列

神仙贪心题。

题目说这么大堆东西就是想告诉你这是个森林，选了\(v\)的父亲后才能选\(v\)。

我们设\(w_v\)为\(v\)所在联通块权值和，\(size_v\)表示\(v\)所在联通块的大小。

我们先考虑单点\(v\)。如果\(v\)是最小的点，那么我们尽量早地将它选了。也就是在选了\(v\)的父亲后就立即选\(v\)。所以我们可以将\(v\)与他的父亲合为一个联通块。

这个结论对于联通块也是成立的，只不过我们要比较平均值。

对于联通块\(u\),\(v\)，如果\(u\)的优先级大于\(v\)，则：

\[ w_u+size_u\cdot w_v<w_v+size_v\cdot w_u\\ \Rightarrow \frac{w_u}{size_u}<\frac{w_v}{size_v} \]

代码：

#include
    
     #define ll long long#define N 500005#define eps 1e-10using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n;int a[N];ll w[N];int f[N],fa[N];int Getf(int v) {return v==f[v]?v:f[v]=Getf(f[v]);}int size[N];struct node {    ll w,s;    int id;    node() {w=s=id=0;}    node(ll x,ll z,int y) {w=x,s=z,id=y;}    bool operator <(const node &a)const {        if(w*a.s!=a.w*s) return w*a.s>a.w*s;        if(w!=a.w) return w
     
      a.id;    }};bool operator ==(const node &a,const node &b) {return a.id==b.id&&a.w==b.w&&a.s==b.s;}struct heap {    priority_queue
      
       add,del;    void Insert(node tem) {add.push(tem);}    void Pop() {while(del.size()&&(del.top())==(add.top())) del.pop(),add.pop();}    void Del(node tem) {        Pop();        del.push(tem);    }    node Top() {        Pop();        return add.top();    }}S;set
       
        s;node tem;int main() {    n=Get();    for(int i=1;i<=n;i++) f[i]=i;    for(int i=1;i<=n;i++) a[i]=Get();    for(int i=1;i<=n;i++) w[i]=Get();    for(int i=1;i<=n;i++) {        if(Getf(a[i])==Getf(i)) {cout<<-1;return 0;}        f[Getf(a[i])]=Getf(i);    }    ll ans=0;    for(int i=0;i<=n;i++) f[i]=i;    for(int i=1;i<=n;i++) {        size[i]=1;        S.Insert(node(w[i],1,i));        ans+=w[i];    }    for(int i=1;i<=n;i++) {        tem=S.Top();        S.Del(tem);        int now=tem.id;        int fa=Getf(a[now]);        if(fa) S.Del(node(w[fa],size[fa],fa));        ans+=size[fa]*w[now];        w[fa]+=w[now];        size[fa]+=size[now];        if(fa) S.Insert(node(w[fa],size[fa],fa));        f[now]=Getf(fa);    }    cout<