首先我们考虑一种n^2logn的做法：将所有的子程序根据内存消耗来排序，然后每一次选中内存消耗最大且尚未被选中的，将所有内存比它小并且可以被同时选中的选中，然后统计贡献。
于是问题转化为如何用logn的复杂度查询祖先-后代关系。
我们考虑将整棵树展开为DFS序列，那么可以用树状数组维护祖先-后代关系。
如何优化这个做法呢？
我们注意到存在一种链的部分分。这种情况是容易解决的：搞两个堆，先把两条子链各自加到堆里，然后每次将它们的堆顶各自提出来，然后取较大值加入最终答案。
这启发我们用类似的方法处理一般的树状情况。
对于任意一个节点，我们建一个堆代表这个节点的子树的数值情况，每一次使用类似链的方法合并。
然而，这样并不能从本质上提升时间复杂度，它仍然需要n^2logn的时间复杂度，只不过不满。
考虑到这是树上的合并问题，因此尝试使用启发式合并，每次只合并两个节点，并将大小较小的那个节点的堆里的东西塞到大小较大的那个节点的堆里。
均摊而言，每个点的位置只会被转移一次——这是因为每一次有且仅有较小的那个堆会被合并，而较大的那个堆不会动。于是，如果一个点被转移了两次，那么一定意味着一个或者更多的节点在这一层的合并中没有被转移。所以均摊共转移不到n次。
对于每一次节点的位置转移，复杂度是logn，因此总复杂度是\(O(n*logn)\)
#include<iostream>
#include<cstdio>
#include<queue>
typedef long long ll;
const int N=200005;
inline void Swap(int &A,int &B){
A^=B^=A^=B;
}
inline int Max(int A,int B){
return A>B?A:B;
}
struct ee{
int v;
int nxt;
}e[N<<1];
int h[N],et=0;
inline void add(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
int fa[N],n;
ll ans=0;
int val[N],id[N],st[N],tp=0;
std::priority_queue<int> q[N];
inline void uni(int X,int Y){
if(q[id[X]].size()<q[id[Y]].size()){
Swap(id[X],id[Y]);
}
while(!q[id[Y]].empty()){
st[++tp]=Max(q[id[X]].top(),q[id[Y]].top());
q[id[X]].pop(),q[id[Y]].pop();
}
while(tp){
q[id[X]].push(st[tp--]);
}
}
inline void dfs(int X){
for(int i=h[X];i;i=e[i].nxt){
dfs(e[i].v);
uni(X,e[i].v);
}
q[id[X]].push(val[X]);
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&val[i]);
id[i]=i;
}
for(int i=2;i<=n;++i){
scanf("%d",&fa[i]);
add(fa[i],i);
}
dfs(1);
while(!q[id[1]].empty()){
ans+=q[id[1]].top();
q[id[1]].pop();
}
printf("%lld\n",ans);
}
int main(){
init();
return 0;
}