Advertisement
yicongli

LG5290

Apr 10th, 2019
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     char gc;x=0;
  12.     while(!isdigit(c))gc;
  13.     while(isdigit(c))x=x*10+c-'0',gc;
  14. }
  15.  
  16. const int N=2e5+7;
  17.  
  18. int a[N];
  19. vector<int>G[N];
  20. priority_queue<int>Q[N];
  21. int tot;
  22. int id[N];
  23. int sta[N];
  24.  
  25. void dfs(int x){
  26.     for(int i=0;i<G[x].size();++i){
  27.         int v=G[x][i];
  28.         dfs(v);
  29.         if(i){
  30.             if(Q[id[x]].size()<Q[id[v]].size()){
  31.                 swap(id[x],id[v]);
  32.             }
  33.             int top=0;
  34.             while(!Q[id[v]].empty()){
  35.                 sta[++top]=max(Q[id[x]].top(),Q[id[v]].top());
  36.                 Q[id[x]].pop();
  37.                 Q[id[v]].pop();
  38.             }
  39.             for(int i=1;i<=top;++i){
  40.                 Q[id[x]].push(sta[i]);
  41.             }
  42.         }
  43.         else {
  44.             id[x]=id[v];
  45.         }
  46.     }
  47.     if(!id[x])id[x]=++tot;
  48.     Q[id[x]].push(a[x]);
  49. }
  50.  
  51. int main(){
  52.     // freopen("spring.in","r",stdin);
  53.     // freopen("spring.out","w",stdout);
  54.     int n;r(n);
  55.     for(int i=1;i<=n;++i){
  56.         r(a[i]);
  57.     }
  58.     for(int i=2;i<=n;++i){
  59.         int x;r(x);
  60.         G[x].push_back(i);
  61.     }
  62.     dfs(1);
  63.     ll ans=0;
  64.     while(!Q[id[1]].empty()){
  65.         ans+=Q[id[1]].top();
  66.         Q[id[1]].pop();
  67.     }
  68.     printf("%lld\n",ans);
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement