Submission #1367806

#TimeUsernameProblemLanguageResultExecution timeMemory
1367806maya_sCat in a tree (BOI17_catinatree)C++20
0 / 100
0 ms344 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dfs(ll node, ll d, vector<vector<ll>> &g, ll &cnt){
    vector<ll> v;
    for(ll i: g[node]) v.push_back(dfs(i, d, g, cnt));
    sort(v.begin(), v.end());
    while(v.size() && v.back() == d) v.pop_back();
    if(v.empty()) {cnt++; return 1;}
    reverse(v.begin(), v.end());
    while(v.size() > 1 && v[v.size()-1] + v[v.size()-2] < d) v.pop_back();
    return v.back() + 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));
    ll cnt = 0;
    dfs(0, k, g, cnt);
    return cnt;
}

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);
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...