#include <bits/stdc++.h> namespace algo { template <typename T, typename F> struct lazy_traits { static void apply(T &a, const F &f, int len) { a = a + f * len; } static void set(T &a, const F &f, int len) { a = f * len; } static void reverse(T &a) {} }; template <typename traits, typename T, typename F> concept has_set_trait = requires(T &a, const F &f, int len) { { traits::set(a, f, len) }; }; } // namespace algo namespace algo { template <typename T, typename f, typename = void> struct monoid_identity; template <typename T> struct monoid_identity<T, std::plus<>, void> { static constexpr T x = T{}; }; template <typename T> struct monoid_identity< T, std::less<>, std::enable_if_t<std::numeric_limits<T>::is_specialized>> { static constexpr T x = std::numeric_limits<T>::max(); }; template <typename T> struct monoid_identity< T, std::greater<>, std::enable_if_t<std::numeric_limits<T>::is_specialized>> { static constexpr T x = std::numeric_limits<T>::min(); }; } // namespace algo namespace algo { namespace internal { template <typename T, typename f = std::plus<>, T base = monoid_identity<T, f>::x, typename F = T, typename traits = lazy_traits<T, F>> class lazy_treap { private: static inline std::mt19937 gen{std::random_device{}()}; struct node { int64_t s, p; node *l, *r; T x, a; F t; bool rev; node(const T &_x) : s(1), p(gen()), l(nullptr), r(nullptr), x(_x), a(_x), t(F{}), rev(false) {} }; T op(const T &a, const T &b) const { if constexpr (std::is_same_v<std::invoke_result_t<f &, T, T>, bool>) { return f{}(a, b) ? a : b; } else { return f{}(a, b); } } node *root; void destruct(node *n) { if (n) { destruct(n->l); destruct(n->r); delete n; } } int64_t s(node *n) const { return n ? n->s : 0; } T a(node *n) { return n ? n->a : base; } void flip(node *n) { if (n) { n->rev ^= 1; } } void __apply(node *n, const F &t) { if constexpr (!std::is_void_v<traits>) { if (n) { traits::apply(n->x, t, 1); traits::apply(n->a, t, n->s); n->t = n->t + t; } } } void pull_rev(node *n) { if (!n) { return; } if (n->rev) { std::swap(n->l, n->r); flip(n->l); flip(n->r); n->rev = false; traits::reverse(n->a); } } void push(node *n) { if (!n) { return; } pull_rev(n); __apply(n->l, n->t); __apply(n->r, n->t); n->t = F{}; } node *pull(node *n) { if (!n) { return n; } pull_rev(n->l); pull_rev(n->r); n->s = s(n->l) + s(n->r) + 1; n->a = op(op(a(n->l), n->x), a(n->r)); return n; } node *build(const std::vector<T> &a) { std::vector<node *> st; st.reserve(a.size()); node *root = nullptr; for (const T &x : a) { node *cur = new node(x); node *prev = nullptr; while (!st.empty() && st.back()->p < cur->p) { prev = st.back(); st.pop_back(); pull(prev); } cur->l = prev; if (!st.empty()) { st.back()->r = cur; } else { root = cur; } st.push_back(cur); } for (int i = st.size() - 1; i >= 0; --i) { pull(st[i]); } return root; } std::pair<node *, node *> split(node *n, int64_t i) { if (!n) { return {nullptr, nullptr}; } if (i < 0) { return {nullptr, n}; } push(n); if (i == s(n->l)) { node *r = std::exchange(n->r, nullptr); return {pull(n), r}; } if (i < s(n->l)) { auto [l, r] = split(std::exchange(n->l, nullptr), i); return {l, merge(r, pull(n))}; } auto [l, r] = split(std::exchange(n->r, nullptr), i - s(n->l) - 1); return {merge(pull(n), l), r}; } node *merge(node *l, node *r) { if (!l) { return r; } if (!r) { return l; } if (l->p < r->p) { push(l); l->r = merge(l->r, r); return pull(l); } push(r); r->l = merge(l, r->l); return pull(r); } node *insert(node *n, int64_t i, const T &x) { auto [l, r] = split(n, i - 1); return merge(merge(l, new node(x)), r); } node *erase(node *n, int64_t i) { auto [l, r1] = split(n, i - 1); auto [m, r] = split(r1, 0); delete m; return merge(l, r); } T at(node *n, int64_t i) { push(n); if (i == s(n->l)) { return n->x; } if (i < s(n->l)) { return at(n->l, i); } return at(n->r, i - s(n->l) - 1); } T _query(int64_t l, int64_t r) { auto [l1, r1] = split(root, l - 1); auto [l2, r2] = split(r1, r - l); T ans = a(l2); root = merge(merge(l1, l2), r2); return ans; } void _apply(int64_t l, int64_t r, const F &x) { auto [l1, r1] = split(root, l - 1); auto [l2, r2] = split(r1, r - l); __apply(l2, x); root = merge(merge(l1, l2), r2); } void _reverse(int64_t l, int64_t r) { auto [l1, r1] = split(root, l - 1); auto [l2, r2] = split(r1, r - l); if (l2) { l2->rev ^= 1; } root = merge(merge(l1, l2), r2); } lazy_treap(node *n) : root(n) {} public: lazy_treap() : root(nullptr) {} lazy_treap(const std::vector<T> &a) { root = build(a); } lazy_treap(std::size_t n, const T &x) { std::vector<T> a(n, x); root = build(a); } lazy_treap(std::size_t n) { std::vector<T> a(n); root = build(a); } lazy_treap(const lazy_treap &) = delete; lazy_treap &operator=(const lazy_treap &) = delete; lazy_treap(lazy_treap &&other) noexcept : root(std::exchange(other.root, nullptr)) {} lazy_treap &operator=(lazy_treap &&other) noexcept { if (this != &other) { destruct(root); root = std::exchange(other.root, nullptr); } return *this; } ~lazy_treap() { destruct(root); } std::size_t size() const { return s(root); } bool empty() const { return size() == 0; } void insert(std::size_t i, const T &x) { root = insert(root, i, x); } void insert(int64_t i, const std::vector<T> &a) { lazy_treap r = split(i - 1); lazy_treap vals(a); merge(vals); merge(r); } void erase(std::size_t i) { root = erase(root, i); } T at(std::size_t i) { return at(root, i); } T back() { return at(size() - 1); } void apply(std::size_t l, std::size_t r, const F &x) requires(!std::is_void_v<traits>) { _apply(l, r, x); } void apply(std::size_t i, const F &x) requires(!std::is_void_v<traits>) { apply(i, i, x); } T query(std::size_t l, std::size_t r) { return _query(l, r); } lazy_treap split(std::size_t i) { auto [l, r] = split(root, i); root = l; return lazy_treap(r); } void merge(lazy_treap &other) { root = merge(root, other.root); other.root = nullptr; } void merge(lazy_treap &&other) { merge(other); } lazy_treap cut(int64_t l, int64_t r) { auto s1 = split(l - 1); merge(s1.split(r - l)); return s1; } void reverse(std::size_t l, std::size_t r) { _reverse(l, r); } }; } // namespace internal } // namespace algo namespace algo { namespace internal { template <typename F> struct lazy_add_set_op { F x, set; bool has_set; lazy_add_set_op() : x(F{}), set(F{}), has_set(false) {} lazy_add_set_op(F x, F set, bool has_set) : x(x), set(set), has_set(has_set) {} lazy_add_set_op operator+(const lazy_add_set_op &o) const { if (o.has_set) { return o; } if (has_set) { return {F{}, set + o.x, true}; } return {x + o.x, F{}, false}; } }; template <typename T, typename F, typename traits> struct lazy_add_set_combine { static void apply(T &a, const lazy_add_set_op<F> &f, int len) { if (f.has_set) { traits::set(a, f.set, len); } else { traits::apply(a, f.x, len); } } static void reverse(T &a) {} }; } // namespace internal } // namespace algo namespace algo { namespace internal { template <typename T, typename Container> struct getter { T operator()(Container *st, std::size_t i) const { return st->at(i); } }; template <typename T, typename Container> struct setter { void operator()(Container *st, std::size_t i, const T &x) const { st->set(i, x); } }; template <typename Container, typename T, typename Getter = getter<T, Container>, typename Setter = setter<T, Container>> struct proxy_ref { Container *st; std::size_t i; proxy_ref(Container *st, std::size_t i) : st(st), i(i) {} proxy_ref(const proxy_ref &) = default; static inline Getter get{}; static inline Setter set{}; operator T() const { return get(st, i); } proxy_ref &operator=(const T &x) { return set(st, i, x), *this; } proxy_ref &operator=(const proxy_ref &r) { return *this = T(r); } template <typename U> requires requires(T a, U b) { a + b; } proxy_ref &operator+=(const U &r) { return set(st, i, T(*this) + r), *this; } template <typename U> requires requires(T a, U b) { a - b; } proxy_ref &operator-=(const U &r) { return set(st, i, T(*this) - r), *this; } template <typename U> requires requires(T a, U b) { a * b; } proxy_ref &operator*=(const U &r) { return set(st, i, T(*this) * r), *this; } template <typename U> requires requires(T a, U b) { a / b; } proxy_ref &operator/=(const U &r) { return set(st, i, T(*this) / r), *this; } T operator++(int) requires std::is_arithmetic_v<T> { T old = *this; set(st, i, old + 1); return old; } T operator--(int) requires std::is_arithmetic_v<T> { T old = *this; set(st, i, old - 1); return old; } proxy_ref &operator++() requires std::is_arithmetic_v<T> { return set(st, i, T(*this) + 1), *this; } proxy_ref &operator--() requires std::is_arithmetic_v<T> { return set(st, i, T(*this) - 1), *this; } friend std::istream &operator>>(std::istream &is, proxy_ref &r) { T x; is >> x; r = x; return is; } friend std::ostream &operator<<(std::ostream &os, const proxy_ref &r) { return os << T(r); } friend T max(const proxy_ref &a, const proxy_ref &b) { return std::max<T>(T(a), T(b)); } friend T max(const proxy_ref &a, const T &b) { return std::max<T>(T(a), b); } friend T max(const T &a, const proxy_ref &b) { return std::max<T>(a, T(b)); } }; template <typename reference, typename Container> class iterator { private: reference ref; public: iterator(Container *st, std::size_t i) : ref(st, i) {} reference &operator*() { return ref; } const reference &operator*() const { return ref; } iterator &operator++() { return ++ref.i, *this; } iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; } bool operator==(const iterator &r) const { return ref.i == r.ref.i && ref.st == r.ref.st; } bool operator!=(const iterator &r) const { return !(*this == r); } }; } // namespace internal } // namespace algo namespace algo { template <typename T, typename f = std::plus<>, T base = monoid_identity<T, f>::x, typename F = T, typename traits = lazy_traits<T, F>> class lazy_add_set_treap { private: using lazy_op = internal::lazy_add_set_op<F>; using combine = internal::lazy_add_set_combine<T, F, traits>; using reference = internal::proxy_ref<lazy_add_set_treap, T>; internal::lazy_treap<T, f, base, lazy_op, combine> treap; lazy_add_set_treap(const internal::lazy_treap<T, f, base, lazy_op, combine> &r) : treap(r) {} public: lazy_add_set_treap() : treap() {} lazy_add_set_treap(const std::vector<T> &a) : treap(a) {} lazy_add_set_treap(std::size_t n, const T &x) : treap(n, x) {} lazy_add_set_treap(std::size_t n) : treap(n) {} void insert(std::size_t i, const T &x) { treap.insert(i, x); } void push_back(const T &x) { insert(size(), x); } void push_front(const T &x) { insert(0, x); } void insert(std::size_t i, const std::vector<T> &a) { treap.insert(i, a); } void erase(std::size_t i) { treap.erase(i); } void pop_back() { erase(size() - 1); } void pop_front() { erase(0); } void add(std::size_t l, std::size_t r, F x) { treap.apply(l, r, {x, F{}, false}); } void add(std::size_t i, F x) { add(i, i, x); } void apply(std::size_t l, std::size_t r, F x) { add(l, r, x); } void apply(std::size_t i, F x) { apply(i, i, x); } void set(std::size_t l, std::size_t r, F x) { treap.apply(l, r, {F{}, x, true}); } void set(std::size_t i, F x) { set(i, i, x); } T query(std::size_t l, std::size_t r) { return treap.query(l, r); } lazy_add_set_treap split(std::size_t i) { return treap.split(i); } void merge(lazy_add_set_treap &r) { treap.merge(r.treap); } void merge(lazy_add_set_treap &&r) { merge(r); } lazy_add_set_treap cut(std::size_t l, std::size_t r) { return treap.cut(l, r); } void reverse(std::size_t l, std::size_t r) { treap.reverse(l, r); } T at(std::size_t i) { return treap.at(i); } reference operator[](std::size_t i) { return reference(this, i); } reference front() { return reference(this, 0); } reference back() { return reference(this, size() - 1); } std::size_t size() const { return treap.size(); } bool empty() const { return treap.empty(); } using iterator = internal::iterator<reference, lazy_add_set_treap>; iterator begin() { return iterator(this, 0); } iterator end() { return iterator(this, size()); } }; template <typename T, typename f = std::plus<>, T base = monoid_identity<T, f>::x, typename F = T, typename traits = lazy_traits<T, F>> using lazy_treap = std::conditional_t<has_set_trait<traits, T, F>, lazy_add_set_treap<T, f, base, F, traits>, internal::lazy_treap<T, f, base, F, traits>>; }; // namespace algo using namespace std; using namespace algo; using treap = lazy_treap<int, greater<>>; 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; } auto dfs = [&](auto &&self, int u) -> treap { treap dp; for (int &i : adj[u]) { treap ndp = self(self, i); ndp.push_front(0); if (ndp.size() > dp.size()) { swap(dp, ndp); } vector<int> qvals(ndp.size()); for (int i = 0; i < ndp.size(); ++i) { if (max(i + 1, d - i) < dp.size()) { qvals[i] = dp.query(max(i + 1, d - i), dp.size() - 1); } } for (int i = 0; i < ndp.size(); ++i) { if (max(i, d - i) < ndp.size()) { dp[i] += ndp.query(max(i, d - i), ndp.size() - 1); } } for (int i = 0; i < ndp.size(); ++i) { dp[i] = max(dp[i], ndp[i]); } for (int i = 0; i < ndp.size(); ++i) { if (max(i + 1, d - i) < dp.size()) { dp[i] = max(dp[i], qvals[i] + ndp[i]); } } } if (dp.empty()) { dp.push_back(1); } else { dp[0] = max(dp[0], (d < dp.size() ? dp[d] : 0) + 1); } return dp; }; treap dp = dfs(dfs, 0); cout << dp.query(0, dp.size() - 1) << '\n'; }