#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 105;
const int maxn=1e4+5;
int n,m,root;
int p[maxn],a[maxn];
int mx[maxn],l[maxn],r[maxn];
vector<int>E[maxn],v;
int dp[maxn][N],ps[maxn];
void dfs(int nd){
mx[nd] = a[nd],l[nd]=r[nd]=nd;
for(auto i : E[nd]){
dfs(i);
if(l[nd] == nd) l[nd] = l[i];
r[nd] = r[i];
mx[nd] = max(mx[nd],mx[i]);
}
if(E[nd].empty()) v.push_back(nd),ps[nd]=(int)v.size()-1;
}
void f(int pos,int nd){
if(nd == 0 or r[nd] != v[pos]) return;
int lft = ps[l[nd]] - 1;
for(int i = 1;i <= min(m,lft + 1);i++)
dp[pos][i] = max(dp[lft][i-1]+mx[nd],dp[pos][i]);
f(pos,p[nd]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> p[i] >> a[i];
if(p[i] == 0) root = i;
else E[p[i]].push_back(i);
}
v.push_back(-1);
dfs(root);
assert((int)v.size()-1 >= m);
for(int i = 0;i < (int)v.size();i++) for(int j = 1;j <= m;j++) dp[i][j] = -1e9;
for(int i = 1;i < (int)v.size();i++){;
f(i,v[i]);
for(int j = 1;j <= m;j++) dp[i][j] = max(dp[i][j],dp[i-1][j]);
}
cout<<dp[(int)v.size()-1][m];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
564 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
948 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
