제출 #1339709

#제출 시각아이디문제언어결과실행 시간메모리
1339709fatelessCat in a tree (BOI17_catinatree)C++20
51 / 100
198 ms14440 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define speedup cin.tie(0)->sync_with_stdio(0);
#define bitcount __builtin_popcount
#define int long long
#define pb push_back
#define vc vector

const int N = 1510, inf = 1e18;
static int dp[N][N];

inline bool chmax (int &a, int b) {if (a < b) {a = b; return 1;} return 0;}
inline void solve() {
    int n, k;
    cin >> n >> k;
    vc<vc<int>> adj (n);
    for (int a = 1; a < n; a++) {
        int b; cin >> b;
        adj[b].pb(a);
    }

    if (k >= n) return cout << 1, void();
    if (k <= 1) return cout << n, void();

    auto dfs = [&](auto &&dfs, int a) -> void {
        for (int b : adj[a]) dfs(dfs, b);
         
        // color it with black
        dp[a][0] = 1;
        for (int b : adj[a]) dp[a][0] += dp[b][k - 1];

        // do not
        for (int d = 1; d <= n; d++) {
            for (int b1 : adj[a]) {
                int cur = dp[b1][d - 1];
                for (int b2 : adj[a]) {
                    if (b1 == b2) continue;
                    cur += dp[b2][max(d - 1, k - d - 1)];
                }

                chmax(dp[a][d], cur);
            }
        }

        for (int d = n; d; d--) chmax(dp[a][d - 1], dp[a][d]);
    }; dfs(dfs, 0);
    cout << dp[0][0];

}

signed main() {
    speedup;
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...