#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
const int maxn = 5e5+10;
int n,m;
vector<int> g[maxn];
int a[maxn];
int cloc = 0;
int tin[maxn];
int arr[maxn];
int tout[maxn];
void dfs(int at, int p) {
assert(cloc<maxn);
arr[cloc] = at;
tin[at] = cloc;
cloc++;
for (int to: g[at]) {
if (to == p) continue;
dfs(to, at);
}
tout[at] = cloc;
}
void setmax(int &x, int y) {
x = max(x, y);
}
int dp[512][maxn];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
int r=-1;
for (int i=1; i<=n; i++) {
int p;
cin>>p;
if (p==0) {
r=i;
} else {
g[p].push_back(i);
}
cin>>a[i];
}
dfs(r,-1);
for (int i=0; i<=cloc; i++) {
for (int j=0; j<=m; j++) {
dp[i][j] = -1e9;
}
}
dp[0][0] = 0;
for (int j=0; j<=m; j++) {
for (int i=0; i<cloc; i++) {
int ptr = tout[arr[i]];
if (j<m) {
setmax(dp[j+1][ptr], dp[j][i]+a[arr[i]]);
}
setmax(dp[j][i+1], dp[j][i]);
}
}
cout<<dp[m][cloc]<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12140 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12140 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12908 KB |
Output is correct |
| 4 |
Runtime error |
47 ms |
17900 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
