Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- const int N = 2e5 + 7;
- int n, d;
- vector <int> g[N];
- vector <int> dp[N];
- void dfs(int u, int p) {
- int mx = -1;
- for (int v : g[u]) {
- if (v != p) {
- dfs(v, u);
- if (mx == -1 || dp[mx].size() < dp[v].size()) {
- mx = v;
- }
- }
- }
- if (mx == -1) {
- dp[u] = {1};
- }
- else {
- swap(dp[u], dp[mx]);
- int uh = dp[u].size();
- int t;
- if (uh < d) t = 1;
- else t = dp[u][uh - d] + 1;
- for (int v : g[u]) {
- if (v != p && v != mx) {
- int vh = dp[v].size();
- for (int i = 0; i + 1 < vh; ++i) {
- dp[v][i + 1] = max(dp[v][i + 1], dp[v][i]);
- }
- vector <int> tmp(vh);
- for (int h = 1; h <= (int)dp[v].size(); ++h) {
- //h <= nh
- int nh = max(h, d - h);
- if (nh <= vh) {
- tmp[vh - h] = max(tmp[vh - h], dp[u][uh - h] + dp[v][vh - nh]);
- }
- }
- for (int nh = 1; nh <= (int)dp[v].size(); ++nh) {
- //h >= nh
- int h = max(nh, d - nh);
- if (h <= uh) {
- tmp[vh - nh] = max(tmp[vh - nh], dp[u][uh - h] + dp[v][vh - nh]);
- }
- }
- for (int h = 1; h <= vh; ++h) {
- dp[u][uh - h] = max(dp[u][uh - h], tmp[vh - h]);
- }
- for (int i = uh - vh; i + 1 < uh; ++i) {
- dp[u][i + 1] = max(dp[u][i + 1], dp[u][i]);
- }
- }
- }
- dp[u].push_back(t);
- for (int v : g[u]) {
- if (v != p && v != mx) {
- int vh = dp[v].size();
- if (vh >= d) {
- dp[u].back() += dp[v][vh - d];
- }
- }
- }
- dp[u][uh] = max(dp[u][uh], dp[u][uh - 1]);
- }
- #ifdef HOME
- cout << u << " : ";
- for (int i = (int)dp[u].size() - 1; i >= 0; --i) cout << dp[u][i] << ' ';
- cout << '\n';
- #endif
- }
- signed main() {
- #ifdef HOME
- freopen("input.txt", "r", stdin);
- #else
- ios_base::sync_with_stdio(0); cin.tie(0); cout.precision(20);
- #endif
- cin >> n >> d;
- for (int i = 1; i < n; ++i) {
- int v;
- cin >> v;
- g[v].push_back(i);
- g[i].push_back(v);
- }
- dfs(0, 0);
- int ans = -1;
- for (int e : dp[0]) ans = max(ans, e);
- cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement