#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n, k;
int root ;
int dp[N][505];
int ans[N] ;
int a[N] ;
vector<int> adj[N] ;
void dfs(int x)
{
int ret = 0;
dp[x][0] = 0 ;
for (auto u : adj[x])
{
dfs(u);
for (int j = 0; j <= k; j++)
{
for (int k1 = 0; k1 <= k; k1++)
{
dp[x][j] = max(dp[x][j], dp[u][k1] + dp[x][k - k1]);
}
}
}
for(int i = k ;i ;i --){
dp[x][i] = max(dp[x][i] , dp[x][i-1] + a[x]) ;
}
ans[x] = max(dp[x][n] , dp[x][n-1] + a[x]) ;
}
int t , st[N] , en[N] , ver[N] ;
int sz[N] ;
int dfz(int x){
sz[x] = 1;
st[x] = ++t ;
ver[t] = x ;
for(auto u : adj[x]){
sz[x]+= dfz(u) ;
}
en[x] = ++ t ;
return sz[x] ;
}
int solve(int x , int r){
if(r > k)
return -N ;
if(x > 2 * n){
if(r == k) return 0 ;
return -N ;
}
if(dp[x][r] != -1)
return dp[x][r] ;
int ret = 0 ;
ret = max(ret , solve(x+1 , r) ) ;
ret = max(ret , solve(x + sz[ver[x]]*2 -1 , r+1 ) + a[ver[x]] ) ;
return dp[x][r] = ret ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("in.in", "r", stdin);
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
int u, c;
cin >> u >> a[i];
if (u)
adj[u].push_back(i);
else
root = i;
}
memset(dp , -1 ,sizeof dp) ;
dfz(root) ;
cout<< solve(root , 0) ;
return 0;
}
Compilation message
biochips.cpp: In function 'void dfs(int)':
biochips.cpp:17:13: warning: unused variable 'ret' [-Wunused-variable]
int ret = 0;
^~~
biochips.cpp: In function 'int main()':
biochips.cpp:74:24: warning: unused variable 'c' [-Wunused-variable]
int u, c;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
105 ms |
200312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
