#include <bits/stdc++.h> namespace algo { /// @brief An iterative segment tree with a fixed size. /// @tparam T Works on any type with a defined associative (but not necessarily /// commutative) operator+, for example, `int` or `algo::min_t`. template <typename T> class segment_tree { private: std::size_t _n, n; std::vector<T> seg; struct accessor { segment_tree &st; std::size_t i; accessor(segment_tree &st, std::size_t i) : st(st), i(i) {} accessor &operator=(const T &x) { st.set(i, x); return *this; } accessor &operator+=(const T &x) { return *this = st.at(i) + x; } accessor &operator-=(const T &x) { return *this = st.at(i) - x; } operator T() const { return st.at(i); } friend std::ostream &operator<<(std::ostream &os, const accessor &acc) { return os << T(acc); } }; public: segment_tree(std::size_t _n) : _n(_n), n(std::bit_ceil(_n)), seg(2 * n) {} segment_tree(const segment_tree &other) : _n(other._n), n(other.n), seg(other.seg) {} segment_tree() : _n(0), n(0) {} segment_tree(std::size_t _n, const T &x) : _n(_n), n(std::bit_ceil(_n)), seg(2 * n) { for (std::size_t i = n; i < n + _n; ++i) { seg[i] = x; } for (std::size_t i = n - 1; i > 0; --i) { seg[i] = seg[2 * i] + seg[2 * i + 1]; } } segment_tree(const std::vector<T> &vals) : _n(vals.size()), n(std::bit_ceil(_n)), seg(2 * n) { set(vals); } /// @brief Sets the value at the `i`-th index to `x`. /// @param i The index at which the value is being modified. /// @param x The new value at that index. void set(std::size_t i, const T &x) { for (seg[i += n] = x, i /= 2; i > 0; i /= 2) { seg[i] = seg[2 * i] + seg[2 * i + 1]; } } /// @brief Bulk-assigns values to all leaves. /// @param vals A vector of size `n`, where `vals[i]` is the value for index `i`. template <typename M> void set(const std::vector<M> &vals) { for (std::size_t i = 0; i < _n; ++i) { seg[n + i] = vals[i]; } for (std::size_t i = n - 1; i > 0; --i) { seg[i] = seg[2 * i] + seg[2 * i + 1]; } } /// @brief Performs associative accumulation. /// @param l The left endpoint (inclusive) of the range to accumulate. /// @param r The right endpoint (inclusive) of the range to accumulate. /// @return Returns the accumulated result of [l, r]. T query(std::size_t l, std::size_t r) const { T ans_l = T{}, ans_r = T{}; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) ans_l = ans_l + seg[l++]; if (r & 1) ans_r = seg[--r] + ans_r; } return ans_l + ans_r; } /// @brief Finds the smallest index r ≥ l such that the predicate returns /// false for the accumulated value over [l, r]. /// @param l The left boundary (inclusive) from which to start the /// accumulation. /// @param t A monotonic predicate that returns true while the accumulated /// range is valid. /// @return The first index r ≥ l such that t(accumulate(l, r)) == false. /// If `t` is true for all r ∈ [l, n), returns n. template <typename Fn> std::size_t min_right(std::size_t l, Fn &&t) const { T p{}; for (l += n; t(p + seg[l]) && l & (l + 1); l /= 2) { if (l & 1) p = p + seg[l++]; } if (t(p + seg[l])) { return _n; } while (l < n) { if (t(p + seg[l <<= 1])) p = p + seg[l++]; } return l - n; } std::size_t size() const { return _n; } std::size_t _size() const { return n; } /// @brief Returns a read-only reference to the value at index `i`. /// @param i The index to access. /// @return A const reference to the element at position `i` in the segment tree (i.e., the leaf at `seg[n + i]`). const T &at(std::size_t i) const { return seg[n + i]; } /// @brief Provides access to the element at index `i` via a proxy object. /// @param i The index to access or update. /// @return A proxy that allows assignment to the element at index `i` /// (calls `update()`), and read access via stream output. accessor operator[](std::size_t i) { return accessor(*this, i); } }; } // namespace algo namespace algo { /// @brief A wrapper type that defines a monoid under the `max` operation. The /// identity element is `std::numeric_limits<T>::min()`. /// @tparam T A numeric type that supports comparison and default construction /// (e.g., `int`, `float`). template <typename T> requires std::is_arithmetic_v<T> struct max_t { T x; constexpr max_t() : x(std::numeric_limits<T>::min()) {} constexpr max_t(const T &x) : x(x) {} constexpr max_t operator+(const max_t &other) const { return std::max(x, other.x); } constexpr operator T() const { return x; } constexpr bool operator==(const max_t &other) const { return x == other.x; } constexpr bool operator!=(const max_t &other) const { return x != other.x; } }; } // namespace algo using namespace std; using namespace algo; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, d; cin >> n >> d; vector<vector<int>> adj(n); for (int i = 1, p; i < n; ++i) { cin >> p; adj[p].push_back(i); } if (d >= n) { cout << "1\n"; return 0; } vector<int> sz(n); auto dfs_sz = [&](auto &&self, int u) -> void { sz[u] = 1; for (int &i : adj[u]) { self(self, i); sz[u] += sz[i]; } }; dfs_sz(dfs_sz, 0); auto dfs = [&](auto &&self, int u) -> deque<int> { segment_tree<max_t<int>> dp(sz[u], 0); for (int &i : adj[u]) { deque<int> _ndp = self(self, i); segment_tree<max_t<int>> ndp(_ndp.size() + 1, 0); for (int i = 1; i <= _ndp.size(); ++i) { ndp[i] = _ndp[i - 1]; } if (ndp.size() > dp.size()) { swap(dp, ndp); } vector<int> qvals; for (int i = 0; i < ndp.size(); ++i) { if (max(i + 1, d - i) < dp.size()) { qvals.push_back(dp.query(max(i + 1, d - i), dp.size() - 1)); } else { qvals.push_back(0); } } for (int i = 0; i < ndp.size(); ++i) { if (max(i, d - i) < ndp.size()) { dp[i] = int{dp.at(i)} + int{ndp.query(max(i, d - i), ndp.size() - 1)}; } } for (int i = 0; i < ndp.size(); ++i) { dp[i] = max(int{dp.at(i)}, int{ndp.at(i)}); } for (int i = 0; i < ndp.size(); ++i) { if (max(i + 1, d - i) < dp.size()) { dp[i] = max(int{dp.at(i)}, qvals[i] + int{ndp.at(i)}); } } } dp[0] = max(int{dp.at(0)}, (d < sz[u] ? int{dp.at(d)} : 0) + 1); deque<int> ret; for (int i = 0; i < dp.size(); ++i) { ret.push_back(int{dp.at(i)}); } return ret; }; deque<int> dp = dfs(dfs, 0); cout << *max_element(dp.begin(), dp.end()) << '\n'; }