联考Day2T2...多亏有这题...让我水了85精准翻盘进了A队...
题目大意：
挺简单的就不说了吧...(这怎么简述啊)
题目思路：
看到题的时候想了半天，不知道怎么搞。把样例画到演草纸上之后又画了几条链手动找最优解，然后发现只需要知道怎么合并子树就行了。因为题目说的很清楚，合并出来链就行，然后手动模拟了一下合并，由于有父子关系的两个点不能被合并在一起，那么从最优的角度考虑显然贪心，把其他链中的最大与当前链最大取\(\max\)，第二大同理，以此类推。那么显然需要一个堆维护，然后考虑合并后的链长度，显然是以\(1\)为一个端点的最长链长。由此很容易想到树剖，先求出重链，然后把轻链合并到重链上。然而考场上蠢了，拿vector维护了链，插入数的时候插入到vector末尾然后暴力swap，结果一条链的时候T了，非常GG。
所以这题真的非常简单，就树剖之后暴力合并，实现细节详见代码qwq(所以要不是因为蠢了就直接A了)
ps:考试的时候写到namespace里面了，然后并不想再改太多，就这样写了，凑合着看一下好了qwq。(这题真的水 就连数据都是水的)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<queue>
using namespace std;
void qread(int &xx){
xx=0;int ch=getchar();
while(ch<'0'||ch>'9'){
ch=getchar();
}
while(ch>='0'&&ch<='9'){
xx=xx*10+ch-'0';
ch=getchar();
}
}
const int N=2e5+5;
int n,M[N],f[N],mxlen[N],lson[N];
vector<int>G[N];
namespace sub1{
void pdfs(int u){
if(!u){
return;
}
for(int v,i=0;i<(int)G[u].size();i++){
v=G[u][i];
pdfs(v);
mxlen[u]=max(mxlen[u],mxlen[v]+1);
}
for(int v,i=0;i<(int)G[u].size();i++){
v=G[u][i];
if(mxlen[v]==mxlen[u]-1){
lson[u]=v;
break;
}
}
mxlen[u]=max(mxlen[u],1);
}
void dfs(int u,priority_queue<int>&pq){
if(!u){
return;
}
if(lson[u]){
dfs(lson[u],pq);
}
else{
pq.push(M[u]);
return;
}
priority_queue<int>rep,repp;
for(int v,i=0;i<(int)G[u].size();i++){
v=G[u][i];
if(v==lson[u]){
continue;
}
dfs(v,rep);
while(!rep.empty()){
repp.push(max(pq.top(),rep.top()));
pq.pop();
rep.pop();
}
while(!repp.empty()){
pq.push(repp.top());
repp.pop();
}
}
pq.push(M[u]);
}
void solve(){
long long rep=0;
priority_queue<int>ans;
pdfs(1);
dfs(1,ans);
while(!ans.empty()){
rep+=ans.top();
ans.pop();
}
printf("%lld\n",rep);
}
}
void addedge(int u,int v){
G[u].push_back(v);
}
int main(){
qread(n);
for(int i=1;i<=n;i++){
qread(M[i]);
}
for(int i=2;i<=n;i++){
qread(f[i]);
addedge(f[i],i);
}
sub1::solve();
return 0;
}