BOI 2017 A code

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define x first
#define y second
using namespace std;
using ll  = long long;
#define int ll
#define mp make_pair

const int N = 2e5 + 10;
const int INF = 1e18;

struct kek {
    int add;
    set<pair<int, int>> q;
    kek() : add(0) {}
    int query(int x) {
        x -= add;
        auto it = q.upper_bound(mp(x, INF));
        if (it == q.begin()) {
            return -INF;
        } else {
            --it;
            return it->y;
        }
    }
    int operator[](int x) {
        return query(x);
    }
    void upd(int x, int y) {
        x -= add;
        if (query(x) >= y) {
            return;
        }
        auto it = q.lower_bound(mp(x, -INF));
        while (it != q.end() && it->y <= y) {
            q.erase(it);
            it = q.lower_bound(mp(x, -INF));
        }
        q.emplace(x, y);
    }
    int size() {
        if (q.empty()) {
            return 0;
        } else {
            return q.rbegin()->x + add + 1;
        }
    }
    void clear() {
        add = 0;
        q.clear();
    }
};

int n;
int d;
vector<int> g[N];
kek dp[N];

void solve(int v) {
    dp[v].upd(0, 1);
    for (int u : g[v]) {
        solve(u);
        kek son = dp[u];
        son.add += 1;
        if (dp[v].size() < son.size()) {
            swap(dp[v].q, son.q);
            swap(dp[v].add, son.add);
        }
        /*
            cerr << "son " << u << endl;
            for (int e : son) {
                cerr << e << " ";
            }
            cerr << endl;
        */
        for (int i = 0; i < (int)son.size(); ++i) {
            int suff = max(i, d - i);
            int value = dp[v][i];
            if (suff < (int)dp[v].size()) {
                dp[v].upd(i, son[i] + dp[v][suff]);
            }
            if (suff < (int)son.size()) {
                dp[v].upd(i, value + son[suff]);
            }
            dp[v].upd(i, son[i]);
        }

            cerr << "after " << u << endl;
            for (auto e : dp[v].q) {
                cerr << e.x + dp[v].add << "\t" << e.y << endl;
            }
            cerr << endl;

        //son.clear();
    }
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> n >> d;
    for (int p, i = 1; i < n; ++i) {
        cin >> p;
        g[p].push_back(i);
    }
    solve(0);
    cout << dp[0][0] << "\n";

    return 0;
}