제출 #1367759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367759		maya_s	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	329 ms	589824 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void dfs(ll node, ll k, vector<vector<ll>> &g, vector<vector<ll>> &dp){
    for(ll i: g[node]) dfs(i, k, g, dp);
    for(ll min_depth = k; min_depth > 0; min_depth--){
        dp[node][min_depth] = dp[node][min_depth+1];
        ll sum_far_enough = 0;
        for(ll i: g[node]) sum_far_enough += dp[i][max(min_depth - 1, k - min_depth - 1)];
        for(ll i: g[node]) dp[node][min_depth] = max(dp[node][min_depth], sum_far_enough - dp[i][max(min_depth - 1, k - min_depth - 1)] + dp[i][min_depth-1]);
    }
    dp[node][0] = dp[node][k]+1;
    for(ll min_depth = k; min_depth >= 0; min_depth--) dp[node][min_depth] = max(dp[node][min_depth], dp[node][min_depth+1]);
}

ll solve(ll n, ll k, vector<vector<ll>> &g){
    if(k >= n) return 0;
    vector<vector<ll>> dp(n, vector<ll>(k+2));
    dfs(0, k, g, dp);
    return dp[0][0];
}

int main(){
    ll n, k; cin >> n >> k;
    vector<vector<ll>> g(n);
    for(ll i = 1; i <= n-1; i++){
        ll p; cin >> p;
        g[p].push_back(i);
    }
    cout << solve(n, k, g);
}

• 서브태스크 1: 11 / 11
• 서브태스크 2: 40 / 40
• 서브태스크 3: 0 / 49