# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
#define pii pair<int,int>
#define debug(x) cout << #x << '=' << x << endl;
const int N = 2e5 + 5;
const int INF = 1e9;
const ll mod = 1e9+7;
int n,m,x[N],now,sz,dp[N][505],z,nilai[N][505];
vector<int>v[N],urutan;
void dfs(int idx){
for(auto isi : v[idx]){
dfs(isi);
}
urutan.pb(idx);
}
int f(int idx,int sisa){
if(sisa == 0) return 0;
if(idx == sz) return -INF;
if(idx >= 0 && dp[v[now][idx]][sisa] != -1) return dp[v[now][idx]][sisa];
int res = f(idx + 1,sisa);
for(int i = 1;i<=m;i++){
if(i > sisa) break;
if(nilai[v[now][idx]][i] == -1) break;
res = max(res,f(idx + 1,sisa - i) + nilai[v[now][idx]][i]);
}
if(idx == -1) return res;
return dp[v[now][idx]][sisa] = res;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen(,r,stdin);
//freopen(,w,stdout);
cin>>n>>m;
for(int i = 1;i<=n;i++){
int p;
cin>>p>>x[i];
v[p].pb(i);
}
dfs(0);
memset(dp,-1,sizeof(dp));
memset(nilai,-1,sizeof(nilai));
for(auto isi : urutan){
now = isi;
sz = v[isi].size();
for(int i = 1;i<=min((int)v[isi].size(),m);i++){
z = i;
nilai[isi][i] = f(-1,i);
}
nilai[isi][1] = max(nilai[isi][1],x[isi]);
}
int ans = 0;
for(int i = 1;i<=n;i++){
ans =max(ans,nilai[i][m]);
}
cout<<ans<<endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
186 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
