Submission #1339546

#TimeUsernameProblemLanguageResultExecution timeMemory
1339546fatelessCat in a tree (BOI17_catinatree)C++20
0 / 100
0 ms344 KiB
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define speedup cin.tie(0)->sync_with_stdio(0)
#define pb push_back

const int INF = 1e9;
int n, D, ans = 0;
vector<vector<int>> adj;
vector<int> f, g;

void dfs(int u, int p) {
    f[u] = INF;
    g[u] = 0; // Сами себя считаем непокрытыми

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        
        // Обновляем состояние из поддеревьев
        g[u] = max(g[u], g[v] + 1);
        f[u] = min(f[u], f[v] + 1);
    }

    // Если ближайшая выбранная вершина покрывает самую дальнюю непокрытую
    if (f[u] + g[u] < D) {
        g[u] = -INF;
    }

    // Если "критическое" расстояние достигнуто — ставим вершину здесь
    if (g[u] == D - 1) {
        ans++;
        f[u] = 0;
        g[u] = -INF;
    }
}

void solve() {
    if (!(cin >> n >> D)) return;
    adj.assign(n, {});
    f.assign(n, 0);
    g.assign(n, 0);
    
    for (int i = 0; i < n - 1; i++) {
        int u = i, v;
        cin >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    if (D == 1) {
        cout << n << endl;
        return;
    }

    ans = 0;
    dfs(0, -1);

    // Если после обхода корня кто-то остался не покрыт — добавляем 1 за корень
    if (g[0] >= 0) ans++;

    cout << ans << endl;
}

int main() {
    speedup;
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...