#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define int long long
const int M = 500005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,cnt,ans,a[M],siz[M],vis[M],fa[M],par[M];
vector<int> g[M];
struct node
{
	int rt,x,y;
	bool operator < (const node &r) const
	{
		return x*r.y>r.x*y;
	}
};priority_queue<node> q;
void dfs(int u,int fa)
{
	vis[u]=1;cnt++;par[u]=fa;
	for(int v:g[u]) if(!vis[v]) dfs(v,u);
}
int find(int x)
{
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		int j=read();
		g[j].push_back(i);
	}
	dfs(0,0);
	if(cnt<=n) {puts("-1");return 0;}
	for(int i=0;i<=n;i++) siz[i]=1,fa[i]=i;
	for(int i=1;i<=n;i++)
		a[i]=read(),q.push(node{i,a[i],1});
	while(!q.empty())
	{
		node t=q.top();int u=t.rt;q.pop();
		if(siz[u]!=t.y) continue;
		int p=fa[u]=find(par[u]);
		ans+=a[u]*siz[p];a[p]+=a[u];siz[p]+=siz[u];
		if(p) q.push(node{p,a[p],siz[p]});
	}
	printf("%lld\n",ans);
}

简单贪心题。

首先判无解，如果有环就一定无解，否则就有解，这一步可以用并查集来判。

然后考虑如何求出答案，我们将 $i$ 连向 $a_i$，连出以 $0$ 为根一颗树。

假设当前的最小值为 $x$，如果 $x$ 点没有父亲，我们肯定直接选了，如果它有父亲，那么也会在父亲选了之后直接选。

于是我们就可以每一次取出权值最小的点（这一步可以用堆或者set实现），然后将这个点和父亲合并，统计新产生的答案。

考虑一个点的权值表示什么。

设有两个序列$A$和$B$，他们的权值和分别为 $w_a,w_b$，他们的大小分别为$siz_a,siz_b$。

• 如果 $AB$ 连接，那么新产生的权值为 $siz_a \times w_b$。
• 如果 $BA$ 连接，那么新产生的权值为 $siz_b \times w_a$。

假设 $AB$ 连接更优，那么 $siz_a \times w_b \ge siz_b \times w_a$

也就是 $\frac{w_a}{siz_a} \le \frac{w_b}{siz_b}$。

那么，我们每一次取出平均权值最小的点即可。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=710000;
int n,a[maxn];
long long w[maxn];
int fa[maxn],siz[maxn];
struct ljq
{
	int x,siz;
	long long w;
	const bool operator < (const ljq &x)const{return w*x.siz>siz*x.w;}
};
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
priority_queue<ljq> S;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void Union(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx==fy)
	{
		puts("-1");
		exit(0);
	}
	fa[fx]=fy;
}
signed main()
{
	n=rd();
	for(int i=0;i<=n;i++)
		fa[i]=i;
	for(int i=1;i<=n;i++)
		a[i]=rd(),Union(i,a[i]);
	for(int i=1;i<=n;i++)
		w[i]=rd(),S.push({i,1,w[i]});
	for(int i=0;i<=n;i++)
		fa[i]=i,siz[i]=1;
	long long ans=0;
	while(!S.empty())
	{
		ljq p=S.top();S.pop();int u;
		if(siz[u=find(p.x)]!=p.siz)
			continue;
		int t=find(a[u]);
		fa[u]=t;
		ans+=1ll*siz[t]*w[u];
		siz[t]+=siz[u],w[t]+=w[u];
		if(t)
			S.push({t,siz[t],w[t]});
	}
	printf("%lld\n",ans);

	return 0;
}