题意简述：将树上 \(n\) 个点划分为若干个集合，使得集合中的点两两没有祖孙关系。一个集合的权值是集合内点的权值的最大值，求所有集合的权值之和的最小值。
首先这题有个非常显然的贪心：将几个权值大的点尽可能的合并到一个集合中是更优的。
集合中的点两两没有祖孙关系，说明集合中的点是在几个不同的子树中取到的。考虑从树上底部往顶部合并。在每个节点上维护一个 堆/set 表示该子树内已经形成的集合（按集合权值从大到小排序）。
合并该节点的两个不同的儿子的堆时（显然分属两个儿子的子树中的点没有祖孙关系），不断的取出两个儿子的堆中最大值，将这两个集合合并为一个集合（根据前文的贪心可知此时为最优），然后再丢回去。
合并堆的时候采用启发式合并算法，时间复杂度是 \(O(n\log n)\) 的。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P__ puts("")
#define PU puts("--------------------")
#define popc __builtin_popcount
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define reprange(a,b,c,d) for(int a=b;a<=c;a+=d)
#define perrange(a,b,c,d) for(int a=b;a>=c;a-=d)
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
#define int long long
//#define int __int128
using namespace std;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
inline void write(int x,char ch='\0'){
if(x<0){x=-x;putchar('-');}
int y=0;char z[40];
while(x||!y){z[y++]=x%10+48;x/=10;}
while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=2e5+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,a[maxn];
vector<int>G[maxn];
priority_queue<int>q[maxn],qq;
int num,num2;
void merge(priority_queue<int>&x,priority_queue<int>&y){
if(x.size()<y.size())swap(x,y);
while(!y.empty()){
num=x.top(),num2=y.top();
x.pop(),y.pop();
qq.push(max(num,num2));
}
while(!qq.empty())x.push(qq.top()),qq.pop();
}
void dfs(int x){
for(int u:G[x])dfs(u),merge(q[x],q[u]);
q[x].push(a[x]);
}
void solve_the_problem(){
n=rd();
rep(i,1,n)a[i]=rd();
rep(i,2,n){int x=rd();G[x].pb(i);}
dfs(1);
int ans=0;
while(!q[1].empty())ans+=q[1].top(),q[1].pop();
write(ans);
}
bool Med;
signed main(){
int _=1;while(_--)solve_the_problem();
}
/*
*/