제출 #1206895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206895		FaresSTH	Biochips (IZhO12_biochips)	C++20	100 / 100	605 ms	404156 KiB

biochips

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
int x[200001],s[200001],dp[200001][501],t[501],n,m,rt;
vector<int>g[200001];
void dfs(int u,int p){
    s[u]=1;
    for(int v:g[u])if(v!=p){
        dfs(v,u);
        s[u]+=s[v];
    }
    int S=s[u];
    for(int v:g[u])if(v!=p){
        for(int i=min(S,m);i>=0;i--){
            for(int j=0;j<=min(s[v],m-i);j++){
                if(dp[u][i+j]<dp[u][i]+dp[v][j]&&(dp[u][i]||i==0))t[i+j]=max(t[i+j],dp[u][i]+dp[v][j]);
            }
        }
        for(int i=0;i<=m;i++)dp[u][i]=max(dp[u][i],t[i]),t[i]=0;
        S+=s[v];
    }
    dp[u][1]=max(dp[u][1],x[u]);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int p,v;
        cin>>p>>v;
        if(p)g[p].push_back(i),g[i].push_back(p);
        else rt=i;
        x[i]=v;
    }
    dfs(rt,0);
    cout<<dp[rt][m];
}

• Subtask 1: 100 / 100