/*
IZhO 12-biochips
This problem can be solved by dynamic programming. At first we will do a
DFS in order to have the DFS order of the tree, keeping the starting and the ending position
for each node's subtrees. Using this information, we will ignore the fact that we can't take ancestors,
focusing only on avoiding to take descendants. Then, we will compute dp[i][j] = max possible sum if we take(or don't take)
the node situated on position i in the dfs order, if we have already taken j nodes so far. So we have 2 cases, we either take
the node and we will consider values taken outside of subtree of node i, or we will take the son's values, whichever is better.
*/
#include<bits/stdc++.h>
using namespace std;
int n, m, root, val[200002];
vector<int>v[200002];
int dp[200002][502], val2[200002], st[200002], sf[200002], poz;
int qq = 0;
void dfs(int nod)
{
++poz;
st[nod] = poz;
val2[poz] = val[nod];
dp[poz][1] = val[nod];
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
dfs(vecin);
}
sf[st[nod]] = poz;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
int parent;
cin >> parent;
cin >> val[i];
if(parent == 0)
root = i;
else
v[parent].push_back(i);
}
dfs(root);
int ans = 0;
for(int i = poz; i >= 1; --i)
for(int j = 1; j <= m; ++j)
{
if(i + 1 <= poz)
dp[i][j] = max(dp[i][j], dp[i+1][j]);
if(sf[i] + 1 <= poz)
dp[i][j] = max(dp[i][j] , dp[sf[i] + 1][j-1] + val2[i]);
if(j == m)
ans = max(ans, dp[i][j]);
}
cout << ans;
return 0;
}
Compilation message
biochips.cpp: In function 'void dfs(int)':
biochips.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
5116 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5288 KB |
Output is correct |
| 4 |
Correct |
25 ms |
22996 KB |
Output is correct |
| 5 |
Correct |
28 ms |
25112 KB |
Output is correct |
| 6 |
Correct |
32 ms |
25152 KB |
Output is correct |
| 7 |
Correct |
424 ms |
298536 KB |
Output is correct |
| 8 |
Correct |
476 ms |
298792 KB |
Output is correct |
| 9 |
Correct |
531 ms |
363064 KB |
Output is correct |
| 10 |
Correct |
634 ms |
400584 KB |
Output is correct |
