C++(g++ 7.5.0) 解法, 执行用时: 223ms, 内存消耗: 8744K, 提交时间: 2022-12-31 20:31:24

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=3e5+10;
LL a[N],b[N],c[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],c[i]=1;
    for(int i=2;i<=n;i++) cin>>b[i];
    for(int i=n;i>=2;i--) c[b[i]]+=c[i];
    sort(a+1,a+1+n);
    sort(c+1,c+1+n);
    LL ans=0;
    for(int i=1;i<=n;i++)
        ans+=a[i]*c[i];
    cout<<ans;
}

C++(clang++ 11.0.1) 解法, 执行用时: 225ms, 内存消耗: 7952K, 提交时间: 2022-12-31 18:22:44

#include<bits/stdc++.h>
using namespace std;
const int m=3e5+10;
long long a[m],b[m],c[m],s=0;
int main()
{
	int n,i;
	cin>>n;
	for(i=1;i<=n;i++) cin>>a[i],c[i]=1;
	for(i=2;i<=n;i++) cin>>b[i];
	for(i=n;i>=2;i--) c[b[i]]+=c[i];
	sort(a+1,a+1+n);
	sort(c+1,c+1+n);
	for(i=1;i<=n;i++) s+=a[i]*c[i];
	cout<<s;
	return 0;
}

pypy3 解法, 执行用时: 423ms, 内存消耗: 60256K, 提交时间: 2022-12-30 21:07:17

n = int(input())
a = list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
for i in range(n):
    p[i] -= 1
cnt = [1] * n
for i in range(1, n)[::-1]:
    cnt[p[i]] += cnt[i]
cnt.sort()
a.sort()
ans = 0
for i in range(n):
    ans += a[i] * cnt[i]
print(ans)
        

Python3 解法, 执行用时: 548ms, 内存消耗: 53464K, 提交时间: 2022-12-30 23:18:30

n = int(input())
a = list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
for i in range(n):
    p[i] -= 1
cnt = [1] * n
for i in range(1, n)[::-1]:
    cnt[p[i]] += cnt[i]
cnt.sort()
a.sort()
ans = 0
for i in range(n):
    ans += a[i] * cnt[i]
print(ans)