| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1300638 | azik21 | Biochips (IZhO12_biochips) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+1 , inf = 1e9;
int dp[N][502] , x[N] , n , k ;
int tin[N] , tout[N] , timer = 0 ;
pair<int ,int >q[N];
vector<int>g[N];
void dfs(int v , int p ){
tin[v] = ++timer;
for(auto it:g[v]){
dfs(it , v);
}
tout[v] = ++timer;
q[timer] = {x[v] , tin[v]};
}
signed main(){
// freopen("d.in" , "r" , stdin);
// freopen("d.out" , "w" , stdout);
// ios_base::sync_with_stdio(0) , cin.tie(0);
cin >> n >> k;
int pr =0 ;
for(int i= 1; i <= n ; i++){
int p;
cin >> p >> x[i];
if(p == 0 )pr =i ;
g[p].pb(i);
}
for(int i= 0 ; i <= n; i++){
for(int j =0 ; j<= k ; j++)dp[i][j] = -inf;
}
for(int i = 1 ; i <= n ; i++){
dp[i][0] = 0 ;
}
dfs(pr , 0 );
for(int i=1 ; i <= timer; i++){
for(int j = 1; j <= k ; j++){
dp[i][j] = dp[i-1][j];
int l = q[i].second , val = q[i].first;
if(l==0)continue;
dp[i][j] = max(dp[i][j] , dp[l-1][j-1]+val);
// cout << i<< ' ' << j << ' ' << dp[i][j] << '\n';
}
// cout << i << ' ' << dp[i] << '\n';
}
cout << dp[timer][k];
}
