fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(v) v.begin(),v.end()
  4. #define MASK(i) (1LL << (i))
  5. #define ii pair<int,int>
  6. #define fi first
  7. #define se second
  8. #define endl '\n'
  9. #define forr(i,l,r,add) for(int i = l;i <= r; i = i + add)
  10. #define fodd(i,l,r,sub) for(int i = l;i >= r ; i = i - sub)
  11. template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;}
  12. template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;}
  13.  
  14. using namespace std;
  15.  
  16. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  17. #define rand rd
  18.  
  19. long long Rand(long long l , long long h){
  20. 	assert(l <= h);
  21. 	return l + 1ll * rd() % (h - l + 1) * (rd() % (h - l + 1)) % (h - l + 1);
  22. }
  23.  
  24.  
  25. //////////////////////////////////////////////////////////// end of template ////////////////////////////////////////////////////////////
  26.  
  27. const int MAX = 1e5 + 5;
  28. int n , a[MAX] , p[MAX];
  29. struct node{
  30.     int w , x , y;
  31. };
  32. vector <node> adj;
  33.  
  34. bool cmp(node x, node y){
  35.     return x.w > y.w;
  36. };
  37.  
  38. ll res[MAX * 2];
  39. int nxt[MAX * 2][2];
  40. int DSU[MAX * 2] , sum[MAX * 2];
  41.  
  42. int par(int u){
  43.     return u == DSU[u] ? u : DSU[u] = par(DSU[u]);
  44. }
  45.  
  46. void INP(){
  47.     cin >> n;
  48.     forr(i , 2 , n , 1){
  49.         cin >> p[i];
  50.     }
  51.     forr(i , 1 , n , 1) cin >> a[i];
  52.     forr(i , 2 , n , 1){
  53.         adj.push_back({min(a[i] , a[p[i]]) , i , p[i]});
  54.     }
  55.     sort(all(adj) , cmp);
  56.     int cnt = n;
  57.     forr(i , 1 , n , 1) DSU[i] = i , sum[i] = 1;
  58.     for(auto wow : adj){
  59.         int w = wow.w , x = wow.x , y = wow.y;
  60.  
  61.         x = par(x) , y = par(y);
  62.         //cout << w << ' ' << x << ' ' << y << endl;
  63.         sum[++cnt] = sum[x] + sum[y];
  64.         DSU[cnt] = cnt;
  65.         DSU[x] = cnt , DSU[y] = cnt;
  66.         res[x] += sum[y] * 1ll * w;
  67.         res[y] += sum[x] * 1ll * w;
  68.         nxt[cnt][0] = x , nxt[cnt][1] = y;
  69.     }
  70.     fodd(i , cnt , n + 1 , 1){
  71.         forr(j , 0 , 1 , 1){
  72.             int x = nxt[i][j];
  73.             res[x] += res[i];
  74.         }
  75.     }
  76.     forr(i , 1 , n , 1) cout << res[i] + a[i] << ' ';
  77. }
  78.  
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(false);
  82.     cin.tie(0);
  83.     cout.tie(0);
  84.     #define TASK ""
  85.     //freopen(TASK".inp" , "r" , stdin);
  86.     //freopen(TASK".out" , "w" , stdout);
  87.     INP();
  88.     return 0;
  89. }
  90.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4PlBUm
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!