#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
const int MAXM=512;
int n,m;
int x[MAXN];
int dp[MAXN][MAXM];
vector<int>g[MAXN];
int tin[MAXN],tout[MAXN],root,t=0,x1[MAXN];
void dfs(int u)
{
tin[u]=++t;
x1[tin[u]]=x[u];
for(auto xd:g[u])
{
dfs(xd);
}
tout[u]=t;
}
vector<int>f[MAXN];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int par;
cin>>par>>x[i];
if(par==0)root=i;
else g[par].push_back(i);
}
dfs(root);
for(int i=1;i<=n;i++)
{
f[tout[i]].push_back(tin[i]);
}
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(auto xd:f[i])
{
for(int j=1;j<=m;j++)
{
if(dp[xd-1][j-1]!=-1)dp[xd][j]=max(dp[xd][j],dp[xd-1][j-1]+x1[xd]);
}
}
for(int j=0;j<=m;j++)
{
if(dp[i-1][j]!=-1)
{
dp[i][j]=max(dp[i][j],dp[i-1][j]);
}
/*if(dp[i][j]!=-1)
{
cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
}*/
}
}
cout<<dp[n][m]<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
233 ms |
410452 KB |
Output is correct |
| 2 |
Incorrect |
180 ms |
410436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
