有思维难度，其实挺好写的。
首先，考虑一条链的情况。
那么根节点最多有两个儿子，分别延伸出两条链。
当且仅当在这两条链中各选择一个点（除了根节点），才不会有祖孙关系。
所以可以贪心地上两个堆。
考虑 \(100\%\) 的数据，那么这个时候就涉及到堆的合并。
于是我们启发式合并。
这个时候，时间复杂度不再是 \(O(n \log^2 n)\) 了。
因为合并的时候，更大的那个，大小应该是其对应子树中的最长链长度。
根据长链剖分的分析，得到 \(O(n \log n)\)。
还有，
pbds 天 下 第 一！
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
using namespace std;
const int N = 2e5;
int n,a[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
long long ans;
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
__gnu_pbds::priority_queue<int> q[N + 5];
int id[N + 5];
int merge(int x,int y)
{
static int buf[N + 5];
if(q[id[x]].size() < q[id[y]].size())
swap(id[x],id[y]);
int m = q[id[y]].size();
for(register int i = 1;i <= m;++i)
buf[i] = max(q[id[x]].top(),q[id[y]].top()),q[id[x]].pop(),q[id[y]].pop();
for(register int i = 1;i <= m;++i)
q[id[x]].push(buf[i]);
return id[x];
}
void dfs(int p,int fa)
{
static int tot = 0;
id[p] = ++tot;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa)
dfs(to[i],p),id[p] = merge(p,to[i]);
q[id[p]].push(a[p]);
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
int u;
for(register int i = 2;i <= n;++i)
scanf("%d",&u),add(u,i);
dfs(1,0);
for(;!q[id[1]].empty();q[id[1]].pop())
ans += q[id[1]].top();
printf("%lld\n",ans);
}