#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n, k;
int root;
int dp[N][55];
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 , 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(1, 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:80:24: warning: unused variable 'c' [-Wunused-variable]
int u, c;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
48128 KB |
Output is correct |
| 2 |
Correct |
29 ms |
48128 KB |
Output is correct |
| 3 |
Correct |
30 ms |
48248 KB |
Output is correct |
| 4 |
Incorrect |
45 ms |
49408 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
