fork download
copy 
  1.     # include <bits/stdc++.h>
  2.     # define pb push_back
  3.     # define eb emplace_back
  4.     # define int long long
  5.     # define f first
  6.     # define s second
  7.     using namespace std;
  8.     vector <int> g[2*100001];
  9.     int sum[2*100001], s[2*100001], ans[2*100001];
  10.     void dfs(int v, int p, int k){
  11.         ans[v] = s[v] * k;
  12.         sum[v] = s[v];
  13.         int mx = 0;
  14.         vector <int> q;
  15.         for(auto i: g[v]){
  16.             dfs(i, v, k / g[v].size());
  17.             ans[v] += ans[i];
  18.              //cout << v << ' ' << i << ' ' << sum[i] << endl;
  19.             q.eb(sum[i]);
  20.         }
  21.         if(g[v].size()){
  22.             // cout << k << ' ' << k % g[v].size() << ' '<< v << ' '<< sum[2] << endl;
  23.             sort(q.begin(), q.end());
  24.             int ptr = g[v].size() - 1;
  25.             for(int j = 1;j <= k % g[v].size();j ++){
  26.                 ans[v] += q[ptr--];
  27.             }
  28.             while(ptr != -1){
  29.                 mx = max(mx , q[ptr --]);
  30.             }
  31.         }
  32.         sum[v] += mx;
  33.     }
  34.     main(){
  35.         int t;
  36.         cin >> t;
  37.         while(t--){
  38.             int n, k;
  39.             cin >> n >> k;
  40.             for(int i = 1;i <= n;i ++) g[i].clear(), sum[i] = 0, ans[i] = 0;
  41.             for(int i = 2;i <= n;i ++){
  42.                 int x;
  43.                 cin >> x;
  44.                 g[x].pb(i);
  45.             }
  46.             for(int i = 1;i <= n;i ++) cin >> s[i];
  47.             dfs(1, 1, k);
  48.             cout << ans[1] << endl;
  49.         }   
  50.     }
Success #stdin #stdout 0.01s 8868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6Lludx
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!