考虑对于a[i]=m,a[m]=n，我们令p[j]=i,p[k]=m（一定会有一对(j,k)满足这个条件的），则我们会有p[k]=a[p[j]]，此时我们要满足k<j，也就是a[m]放的位置要比a[i]靠前。

也就是说选第m个之后才能选第i个。

转换成图论模型就是m->i <=> a[i]->i。

那么问题豁然开朗，首先如果图中有环就能判断无解了。

如果有解则必然为以0为根的有向树，则答案为每个节点i被拿到的时间*w[i]（前提是i的父亲被拿才可以拿i）。

再考虑最大化答案，则我们让树中最小值min尽可能早的被拿到就好了。

继续贪心，则如果当前局面能够拿到min则一定拿min，换句话将就是拿了min的父亲就一定拿min。

那么父亲和min之间就成了捆绑关系，于是将其缩起来，在缩的过程中更新答案，然后递归这个过程就好了。

每次找min可以用堆维护，复杂度O(nlogn)。

（PS：更新答案，每次更新显然是这个点前面一些点被选了，于是它一定产生了前面这些点个数*w[该点]的价值）

那么就需要考虑我们缩完的点的w要怎么计算，对于两个集合a，b要合并，显然用在计算上的w=wa+wb，但是用堆排序的时候就不能这么做了。

自然能想到取平均值，虽然我不会证明，不过考量一下发现差不多。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;typedef long long ll;typedef long double dl;typedef pair
              
               pii;#define fi first#define se secondtypedef __gnu_pbds::priority_queue
               
                
                 ,__gnu_pbds::pairing_heap_tag> heap;const int N=5e5+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int to,nxt;}e[N];int n,cnt,head[N],vis[N],a[N],num,fa[N],size[N];ll w[N],ans;heap::point_iterator id[N];heap q;inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}bool dfs(int u){ vis[u]=1;num++; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(vis[v]||!dfs(v))return 0; } if(!u&&num<=n)return 0; return 1;}inline int find(int x){ if(x==fa[x])return x; return fa[x]=find(fa[x]);}int main(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(),add(a[i],i); for(int i=1;i<=n;i++)w[i]=read(); if(!dfs(0)){puts("-1");return 0;} for(int i=0;i<=n;i++)fa[i]=i,size[i]=1; for(int i=1;i<=n;i++)id[i]=q.push(pii(w[i],i)); while(!q.empty()){ int u=q.top().se,v=a[u];q.pop(); int rt=find(v); ans+=w[u]*size[rt]; fa[u]=rt;w[rt]+=w[u];size[rt]+=size[u]; if(rt)q.modify(id[rt],pii((dl)w[rt]/size[rt],rt)); } printf("%lld\n",ans); return 0;}
                
               
              
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++