fork download 
  1. #include<cstdio>
  2. #include<vector>
  3. using namespace std;
  4. #define INF 1000000000
  5.  
  6. #define N 100010
  7. #define M 110
  8. int w[N], si[N], loli[N], dp[N][M];
  9. vector<int> g[N];
  10.  
  11. int dfs(int u, int p=0){
  12.     static int cnt;
  13.     if(!p){
  14.         cnt = 0;
  15.     }
  16.     int size = 1;
  17.     for(int v: g[u]){
  18.         if(v==p) continue;
  19.         size += dfs(v, u);
  20.     }
  21.     si[++cnt] = u;
  22.     loli[cnt] = cnt-size;
  23.     return size;
  24. }
  25.  
  26. int main(){
  27.     int n, K;
  28.     while(scanf("%d%d", &n, &K), n){
  29.         for(int i=1; i<=n; i++){
  30.             scanf("%d", w+i);
  31.         }
  32.         for(int i=2; i<=n; i++){
  33.             int v;
  34.             scanf("%d", &v); v++;
  35.             g[i].push_back(v);
  36.             g[v].push_back(i);
  37.         }
  38.         dfs(1);
  39.         dp[0][0] = 0;
  40.         fill(dp[0]+1, dp[0]+K+1, -INF);
  41.         for(int i=1; i<=n; i++){
  42.             dp[i][0] = 0;
  43.             for(int j=1; j<=K; j++){
  44.                 dp[i][j] = max(dp[i-1][j], w[si[i]]+dp[loli[i]][j-1]);
  45.             }
  46.         }
  47.         int ans = dp[n][1];
  48.         for(int i=2; i<=K; i++){
  49.             ans = max(ans, dp[n][i]);
  50.         }
  51.         printf("%d\n", ans);
  52.         for(int i=1; i<=n; i++){
  53.             g[i].clear();
  54.         }
  55.     }
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0s 4940KB
comments (?)
stdin 
7 3
6 3 4 -1 1 -5 1
0 1 1 0 0 5
2 1
-1 1
0
3 3
1 2 3
0 0
8 8
1 2 3 4 5 6 7 8
0 1 2 3 4 5 6
4 4
-27 -45 -67 -98
2 0 2
0 0
stdout 
6
1
5
8
-27
https://ideone.com/R3eeRb
language:
C++14 (gcc 8.3)
created:
6 years 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!