Submission #1244558

#TimeUsernameProblemLanguageResultExecution timeMemory
1244558CrabCNHCat in a tree (BOI17_catinatree)C++20
100 / 100
59 ms20808 KiB
#include <bits/stdc++.h>

using namespace std;

const int maxN = 2e5 + 5;
const int inf = 1e9 + 7;

int n, D;
int a[maxN];
vector <int> adj[maxN];
int miDepth[maxN], dp[maxN];

void dfs (int u, int p) {
    miDepth[u] = inf;
    for (auto v : adj[u]) {
        if (v == p) {
            continue;
        }
        dfs (v, u);
        if (miDepth[u] + miDepth[v] + 1 >= D) {
            dp[u] += dp[v];
            miDepth[u] = min (miDepth[u], miDepth[v] + 1);
        }
        else {
            dp[u] += dp[v] - 1;
            miDepth[u] = max (miDepth[u], miDepth[v] + 1);
        }
    }
    if (miDepth[u] >= D) {
        dp[u] ++;
        miDepth[u] = 0;
    }
}

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cin >> n >> D;
    for (int i = 1; i <= n - 1; i ++) {
        int p;
        cin >> p;
        adj[i].push_back (p);
        adj[p].push_back (i);
    }
    dfs (0, 0);
    cout << dp[0];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...