Submission #1208382

#TimeUsernameProblemLanguageResultExecution timeMemory
1208382m5588ohammedBiochips (IZhO12_biochips)C++20
0 / 100
2100 ms108928 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define mod 1000000007 int dp[200001][501],leafs[200001],n,m,arr[200001],rt; vector <array<int,2>> v[200001]; void build(int i){ if(v[i].size()==0){ leafs[i]=1; return; } for(auto [j,c]:v[i]){ build(j); leafs[i]+=leafs[j]; } return; } void calc(int i){ for(int k=0;k<=m;k++) dp[i][k]=-1e9; dp[i][1]=arr[i]; dp[i][0]=0; for(auto [j,lef]:v[i]){ calc(j); for(int k=0;k<=leafs[i];k++){ for(int p=0;p<=min(k,leafs[j]);p++){ dp[i][k]=dp[i][k-p]+dp[j][p]; if(dp[i][k]<0) dp[i][k]=-1e9; } } } return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(int i=1;i<n;i++){ int p; cin>>p>>arr[i]; if(p==0) rt=i; else v[p].push_back({i,0}); } build(rt); for(int i=1;i<=n;i++){ for(int j=0;j<v[i].size();j++) v[i][j][1]=leafs[v[i][j][0]]; sort(v[i].begin(),v[i].end()); } calc(rt); cout<<dp[rt][m]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...