Luogu

分析

首先，如果 $a[j]=k$ ，那么 $k$ 一定在 $j$ 的前面。

考虑从 $a[j]$ 向 $j$ 连边，构成一个图。显然，如果有环的话是无解的，

那么现在就是，如果要选子节点，必须要先选父节点。$i$ 节点第 $T$ 个选出来的话，贡献是 $Tw[i]$ 。

考虑贪心。设当前权值最小的节点为 $i$。

  • 如果 $i$ 没有父节点的话，显然当前会选 $i$ 。
  • 如果 $i$ 有父节点，那么当 $i$ 的父节点选了之后一定会选 $i$，也就是说最后的排列中 $fa[i]$ 和 $i$ 挨在一起。那么我们可以把这两个点合并。

考虑合并后每次应该取怎样的元素。一个长度为 $l_1$ 的序列 $a$ 和一个长度为 $l_2$ 的序列 $b$，通过邻项交换法可以得到如果 $\frac{W_a}{l_1}<\frac{W_b}{l_2}$，那么拼成 $ab$ 会更优，即平均权值小的点放前面会更优。

那么可以每次取出平均权值最小的点，然后将它与它的父节点合并，同时将产生的 $W_b\times l_a$ 的贡献计入答案即可。

每次要取出一个最小值，可以用一个堆来维护。然后要支持修改，可以随便拿个东西作为标记来解决。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,tot=0;
ll w[N];
int fa[N],f[N],sz[N],vis[N];

struct Edge { int v,nxt; } e[N];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

inline void dfs(int u) {
    vis[u]=1,++tot;
    for (re int i=head[u];i;i=e[i].nxt) {
        if (vis[e[i].v]) { puts("-1"); exit(0); }
        else dfs(e[i].v);
    }
}

inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

struct node { int u,sz; ll w; };
bool operator <(node a,node b) { return a.w*b.sz>b.w*a.sz; }

priority_queue<node> Q;

int main() {
    n=read();
    for (re int i=1;i<=n;++i) fa[i]=read(),addEdge(fa[i],i);
    for (re int i=1;i<=n;++i) w[i]=read();
    dfs(0); if (tot<=n) { puts("-1"); return 0; }
    for (re int i=0;i<=n;++i) f[i]=i,sz[i]=1;
    for (re int i=1;i<=n;++i) Q.push((node){i,1,w[i]});
    ll ans=0;
    while (!Q.empty()) {
        node x=Q.top(); Q.pop();
        int u=find(x.u);
        if (sz[u]!=x.sz) continue;
        int p=find(fa[u]); f[u]=p;
        ans+=w[u]*sz[p],w[p]+=w[u],sz[p]+=sz[u];
        if (p) Q.push((node){p,sz[p],w[p]});
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改：2021 年 03 月 23 日 05 : 37 PM
© 允许规范转载