#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n,m;
vector<int> adj[N];
int par[N];
int arr[N];
int ans = 0;
vector<int> dfs(int v,int c,vector<int> dp){
dp[0] = 0;
vector<int> tmp = dp;
for(auto u:adj[v]){
if(u == c)continue;
dp = dfs(u,-1,dp);
}
if(c == -1){
for(int i=1;i<=m;i++){
dp[i] = max(dp[i],tmp[i-1]+arr[v]);
}
}
else{
dp[1] = max(dp[1],arr[v]);
}
ans = max(ans,dp[m]);
if(c != -1 && par[v]){
dfs(par[v],v,dp);
}
return dp;
}
void solve(){
cin >> n >> m;
int root = 0;
for(int i=1;i<=n;i++){
cin >> par[i] >> arr[i];
if(par[i] == 0)root = i;
else adj[par[i]].push_back(i);
}
for(int i=1;i<=n;i++){
if(adj[i].empty()){
dfs(i,0,vector<int>(m+1,-1e9));
break;
}
}
cout << ans << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
Compilation message
biochips.cpp: In function 'void solve()':
biochips.cpp:32:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
32 | int root = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4976 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5196 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5196 KB |
Output is correct |
| 7 |
Correct |
107 ms |
7256 KB |
Output is correct |
| 8 |
Correct |
110 ms |
7244 KB |
Output is correct |
| 9 |
Correct |
131 ms |
10660 KB |
Output is correct |
| 10 |
Correct |
169 ms |
11616 KB |
Output is correct |
