제출 #711421

#제출 시각아이디문제언어결과실행 시간메모리
711421stevancvCat in a tree (BOI17_catinatree)C++14
100 / 100
83 ms23360 KiB
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
vector<int> g[N];
int k;
pair<int, int> Dfs(int s) {
    vector<int> v;
    v.push_back(0);
    int ans = 1;
    for (int u : g[s]) {
        auto x = Dfs(u);
        ans += x.first;
        v.push_back(x.second);
    }
    sort(v.rbegin(), v.rend());
        while (v.size() >= 2 && v.back() + v[v.size() - 2] < k) {
        ans -= 1;
        v.pop_back();
    }
    return {ans, v.back() + 1};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int p; cin >> p;
        g[p].push_back(i);
    }
    cout << Dfs(0).first << en;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...