제출 #1296417

#제출 시각아이디문제언어결과실행 시간메모리
1296417rayan_bdCat in a tree (BOI17_catinatree)C++20
100 / 100
38 ms18608 KiB
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int mxN = 2e5 + 10;
pair<int, int> dp[mxN];
vector<int> adj[mxN];
int n, d;
void dfs(int u = 0){
    vector<int> v;
    int tot = 0, dist = 1e9;
    for(auto it : adj[u]){
        dfs(it);
        tot += dp[it].fi;
        v.push_back(dp[it].se + 1);
    }
    sort(v.begin(), v.end());
    if(!v.size()){
        dp[u].fi = 1, dp[u].se = 0;
    }else{
        dist = v[0];
        for(int i = 1; i < v.size(); ++i){
            if(v[i] + dist < d){
                --tot, dist = v[i];
            }
        }
        if(dist >= d) dp[u].fi = ++tot, dp[u].se = 0;
        else dp[u].fi = tot, dp[u].se = dist;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> d;
    for(int i = 1, p; i < n; ++i){
        cin >> p;
        adj[p].push_back(i);
    }
    dfs();
    cout << dp[0].fi << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...