제출 #1339535

#제출 시각아이디문제언어결과실행 시간메모리
1339535Lakshya108Cat in a tree (BOI17_catinatree)C++20
100 / 100
43 ms19300 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()

const int N = 2e5+5;
ll n,d;
vector<ll> g[N];
pair<ll,ll> dp[N];

void dfs(ll u){
    vector<ll> v;
    ll tot=0;
    for(auto x:g[u]){
        dfs(x);
        tot+=dp[x].first;
        v.push_back(dp[x].second+1);
    }
    sort(all(v));
    if(v.empty()){
        dp[u]={1,0};
        return;
    }
    ll dist=v[0];
    for(ll i=1;i<v.size();i++){
        if(v[i]+dist<d){
            tot--;
            dist=v[i];
        }
    }
    if(dist>=d) dp[u]={tot+1,0};
    else dp[u]={tot,dist};
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>d;
    for(ll i=1,p;i<n;i++){
        cin>>p;
        g[p].push_back(i);
    }
    dfs(0);
    cout<<dp[0].first;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...