补题【牛客小白月赛64】D
作者:
莫德歪奇
,
2023-01-08 23:22:29
,
所有人可见
,
阅读 146
https://ac.nowcoder.com/acm/contest/49244/D
[排序不等式][单链表]
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 3e5 + 10;
int e[N], ne[N], idx, h[N];
int num[N],a[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
num[u] = 1;
for (int i = h[u]; i != -1; i=ne[i])
{
int j = e[i];
dfs(j);
num[u] += num[j];
}
}
int main()
{
int n;
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 2; i <= n; i++)
{
int x;
cin >> x;
add(x, i);
}
dfs(1);
sort(a + 1, a + n + 1);
sort(num + 1, num + n + 1);
long long sum = 0;
for (int i = 1; i <= n; i++)
{
sum += (long long)a[i] * num[i];
}
cout << sum << endl;
return 0;
}