#include <bits/stdc++.h>
#ifndef LOCAL_RUN
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("avx2,tune=native")
#endif
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
if(b==0)return 1;
if(b%2==0){
ll t=bin_pow(a,b/2);
return t*t%MOD;
}
else return a*bin_pow(a,b-1)%MOD;
}
vector<ll>graph[200000];
int dp[200000][501],a[200000];
bool used[200000];
int t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0;
void dfs(ll v,ll p=-1){
used[v]=true;
if(graph[v].size()==1){
dp[v][1]=a[v];
return;
}
for(auto u : graph[v]){
if(used[u])continue;
dfs(u,v);
}
for(auto u : graph[v]){
if(u==p)continue;
vector<ll>c(m+1);
for(int j=0;j<=m;j++){
for(int i=j;i<=m;i++){
//if(v==2&&u==4&&i==2)cout<<j<<" "<<dp[4][1]<<dp[2]<<"ss"<<endl;
c[i]=max(ll(dp[v][i-j]+dp[u][j]),c[i]);
}
}
for(int z=m;z>=0;z--){
dp[v][z]=c[z];
}
}
dp[v][1]=a[v];
for(auto u : graph[v]){
if(u==p)continue;
dp[v][1]=max(dp[v][1],dp[u][1]);
}
}
int main()
{
//freopen("stones.in","r",stdin);
//freopen("stones.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>x>>y;
x--;
a[i]=y;
if(x==-1){
z=i;
continue;
}
graph[i].push_back(x);
graph[x].push_back(i);
}
dfs(z);
ans=dp[z][m];
//cout<<dp[2][2]<<endl;
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5228 KB |
Output is correct |
| 4 |
Correct |
41 ms |
22892 KB |
Output is correct |
| 5 |
Correct |
56 ms |
25068 KB |
Output is correct |
| 6 |
Correct |
82 ms |
25196 KB |
Output is correct |
| 7 |
Execution timed out |
2068 ms |
152192 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
