思路 **先考慮一條鏈的情況怎麼做。** 因為只有兩個子樹,並且兩個子樹都是鏈。所以可以把這兩條鏈找出來,然後$sort$一下。合併起來。 **然後推廣到樹上** 對於每一棵樹都可以按照和上面同樣的方法合併成一條鏈。 ...
思路
先考慮一條鏈的情況怎麼做。
因為只有兩個子樹,並且兩個子樹都是鏈。所以可以把這兩條鏈找出來,然後\(sort\)一下。合併起來。
然後推廣到樹上
對於每一棵樹都可以按照和上面同樣的方法合併成一條鏈。
這樣就可以\(O(n^2logn)\)做了。
考場上就想到這些。而且鏈的情況還忘了存檔。。。
啟髮式合併
只要對於每個節點維護出一個堆,並且進行啟髮式合併。就可以達到\(O(nlogn)\)的複雜度了。
還是太菜了。。。
代碼
/*
* @Author: wxyww
* @Date: 2019-04-11 20:14:14
* @Last Modified time: 2019-04-11 20:23:59
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 200000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
priority_queue<int>q[N];
vector<int>e[N];
int a[N],dy[N];
int tmp[N];
int merge(int x,int y) {
if(q[x].size() < q[y].size()) swap(x,y);
int js = 0;
while(!q[y].empty()) {
tmp[++js] = max(q[y].top(),q[x].top());
q[y].pop();q[x].pop();
}
for(int i = 1;i <= js;++i) q[x].push(tmp[i]);
return x;
}
void dfs(int u) {
int k = e[u].size();
dy[u] = u;
for(int i = 0;i < k;++i) {
int v = e[u][i];
dfs(v);
dy[u] = merge(dy[u],dy[v]);
}
q[dy[u]].push(a[u]);
}
int main() {
int n = read();
for(int i = 1;i <= n;++i) a[i] = read();
for(int i = 2;i <= n;++i) e[read()].push_back(i);
dfs(1);
ll ans = 0;
while(!q[dy[1]].empty()) {
ans += q[dy[1]].top();q[dy[1]].pop();
}
cout<<ans;
return 0;
}