fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define vi vector<int>
  5. #define fi first
  6. #define se second
  7. #define pb push_back
  8. #define ii pair<int , int>
  9. #define pq priority_queue
  10. #define iii pair<int , pair<int , int>>
  11. #define fo(i,l,r) for(int i=l;i<=r;i++)
  12. #define fod(i,r,l) for(int i=r;i>=l;i--)
  13. #define fill(f,x) memset(f,x,sizeof(f))
  14. #define NAME "file"
  15.  
  16. const int N = 2e5 + 5, mod = 1e9 + 7;
  17. int n;
  18. vector <int> g[N];
  19. int w[N] , dp[N][2] , s[N] , node[N] , p[N] , cnt = 0;
  20.  
  21. void dfs1(int u , int pa)
  22. {
  23.     s[u] = w[u];
  24.     node[u] = 1;
  25.  
  26. 	for (auto v : g[u]) 
  27. 	if (v != pa) 
  28. 	{
  29. 		dfs1(v , u);
  30.  
  31.         s[u] += s[v];
  32.         node[u] += node[v];
  33.     }
  34. }
  35.  
  36. bool cmp(int a , int b)
  37. {
  38.     return s[a] * node[b] < s[b] * node[a];
  39. }
  40.  
  41. void dfs2(int u , int pa)
  42. {
  43.     vector <int> g2; // chua cac con 
  44.     p[u] = ++cnt;
  45.  
  46. 	for (auto v : g[u]) 
  47. 	if (v != pa) 
  48. 	{
  49. 		g2.push_back(v);
  50.     }
  51.  
  52.     sort(g2.begin() , g2.end() , cmp);
  53.  
  54.     for (auto v : g2)
  55.     {
  56.         dfs2(v , u);
  57.     }
  58. }
  59.  
  60.  
  61. signed main()
  62. {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0);  cout.tie(0);
  65.     //freopen(NAME".INP" , "r" , stdin);
  66.     //freopen(NAME".OUT" , "w" , stdout);
  67.  
  68.     cin >> n;
  69.     fo(i, 1, n)
  70.         cin >> w[i];
  71.  
  72.     fo(i, 2, n)
  73.     {
  74.         int p;
  75.         cin >> p;
  76.         g[p].push_back(i);
  77.     }
  78.  
  79.     dfs1(1 , 0);
  80.     dfs2(1 , 0);
  81.  
  82.     int ans = 0;
  83.     fo(i, 1, n)
  84.         ans += p[i] * w[i];
  85.     cout << ans;
  86. }
  87. // haronnee_
Success #stdin #stdout 0.01s 13512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wKBnKe
language:
C++ (gcc 8.3)
created:
3 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!