Submission #1322519

#TimeUsernameProblemLanguageResultExecution timeMemory
1322519TsaganaCat in a tree (BOI17_catinatree)C++20
0 / 100
1 ms332 KiB
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define S second
#define F first

using namespace std;

int n, d;
vector<int> adj[200010];
int lvl[200010];
int R, mx, ans;

void dfs(int s, int p) {
    if (lvl[s] > mx) {
        mx = lvl[s];
        R = s;
    }
    for (auto i: adj[s]) {
        if (i == p) continue ;
        lvl[i] = lvl[s] + 1;
        dfs(i, s);
    }
}

void calc(int s, int p) {
    if (lvl[s] >= d) {
        lvl[s] = 0;
        ans++;
    }
    for (auto i: adj[s]) {
        if (i == p) continue ;
        lvl[i] = lvl[s] + 1;
        calc(i, s);
        lvl[s] = min(lvl[s], lvl[i] + 1);
    }
}

void solve() {
    cin >> n >> d;
    for (int i = 1; i < n; i++) {
        int x; cin >> x;
        adj[x].pb(i);
        adj[i].pb(x);
    }
    lvl[0] = 1;
    dfs(0, -1);
    mx = 0;
    lvl[R] = 1;
    dfs(R, -1);
    mx = 0;
    lvl[R] = d;
    ans = 0;
    calc(R, -1);
    cout << ans << '\n';
}

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