Submission #1296254

#TimeUsernameProblemLanguageResultExecution timeMemory
1296254avighnaCat in a tree (BOI17_catinatree)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>

using namespace std;

class segment_tree {
private:
  int n;
  vector<int> seg;

public:
  segment_tree(int n) : n(n), seg(2 * n) {}

  int query(int l, int r) {
    int ans = 0;
    for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        ans = max(ans, seg[l++]);
      if (r & 1)
        ans = max(ans, seg[--r]);
    }
    return ans;
  }

  void set(int i, int x) {
    for (seg[i += n] = x, i >>= 1; i > 0; i >>= 1) {
      seg[i] = max(seg[2 * i], seg[2 * i + 1]);
    }
  }
};

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> {
    vector<deque<int>> ch;
    for (int &i : adj[u]) {
      ch.push_back(self(self, i));
      ch.back().push_front(0);
    }
    deque<int> dp(sz[u]);
    segment_tree st(sz[u]);
    auto set = [&](int i, int x) { st.set(i, dp[i] = x); };
    auto max_suff = [&](int i) { return st.query(i, sz[u] - 1); };
    for (auto &ndp : ch) {
      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] = max_suff(max(i + 1, d - i));
        }
      }
      vector<int> suff_ndp(ndp.size());
      suff_ndp.back() = ndp.back();
      for (int i = ndp.size() - 2; i >= 0; --i) {
        suff_ndp[i] = max(ndp[i], suff_ndp[i + 1]);
      }
      for (int i = 0; i < ndp.size() - 1; ++i) {
        if (max(i, d - i) < ndp.size()) {
          set(i, dp[i] + suff_ndp[max(i, d - i)]);
        }
      }
      for (int i = 0; i < ndp.size(); ++i) {
        set(i, max(dp[i], ndp[i]));
      }
      for (int i = 0; i < ndp.size(); ++i) {
        if (max(i + 1, d - i) < dp.size()) {
          set(i, max(dp[i], qvals[i] + ndp[i]));
        }
      }
    }
    dp[0] = max(dp[0], (d < sz[u] ? dp[d] : 0) + 1);
    return dp;
  };

  deque<int> dp = dfs(dfs, 0);
  cout << *max_element(dp.begin(), dp.end()) << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...