Submission #1206884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206884		basa	Biochips (IZhO12_biochips)	C++20	100 / 100	547 ms	409156 KiB

biochips

#include <bits/stdc++.h>

using namespace std;

const int M = 505;
const int maxn = 2e5 + 5;

int n, m;
int sz[maxn];
int val[maxn];
int dp[maxn][M];
vector<int>adj[maxn];

void calcsz(int v, int p){
  for(int i : adj[v]){
    if(i == p) continue;
    calcsz(i, v);
    sz[v] += sz[i];
  }
  sz[v] += adj[v].size();
}

void dfs(int v, int p){
  int tmp[m + 5] = {};

  int cnt = 0;
  for(int i : adj[v]){
    if(i == p) continue;
    dfs(i, v);
    cnt++;

    for(int j = 1; j <= min(m, sz[v]); j++){
      for(int k = 0; k <= min(j, sz[i]); k++){
        int l = j - k;
        dp[v][j] = max(dp[i][k] + tmp[l], dp[v][j]);
      }
    }

    for(int j = 1; j <= min(m, sz[v]); j++) tmp[j] = dp[v][j];
  }

  dp[v][1] = max(dp[v][1], val[v]);
}

signed main()
{
  cin.tie(0) -> sync_with_stdio(0);
  cin >> n >> m;

  int rt;
  for(int i = 1; i <= n; i++){
    int p, w;
    cin >> p >> w;

    if(p == 0) rt = i;

    val[i] = w;
    adj[i].push_back(p);
    adj[p].push_back(i);
  }

  calcsz(rt, 0);
  dfs(rt, 0);
  cout << dp[rt][m];
}

• Subtask 1: 100 / 100