Submission #1301451

#TimeUsernameProblemLanguageResultExecution timeMemory
1301451nguynCat in a tree (BOI17_catinatree)C++20
100 / 100
63 ms33332 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 1e6 + 5;

int n, k;
vector<int> g[N]; 

ll res;

struct Deque{
    vector<int> a;
    int size(){ return (int)a.size(); }
    void push_front(int x){
        a.push_back(x);
    }
    int& operator [] (int x){
        return a.rbegin()[x];
    }
    void clear(){
        vector<int>().swap(a);
    }
} f[N];

void dfs(int u, int p) {
	f[u].push_front(1); 
	for (int v : g[u]) {
		if (v == p) continue;
		dfs(v, u); 
		f[v].push_front(1); 
		if (f[u].size() < f[v].size()) swap(f[u], f[v]); 
        
        for (int i = 0; i < f[v].size(); i++) {
            int x = f[v][i] + (max(i, k - i + 1) < f[u].size() ? f[u][max(i, k - i + 1)] : 0); 
            int y = f[u][i] + (max(i, k - i + 1) < f[v].size() ? f[v][max(i, k - i + 1)] : 0); 

            f[u][i] = max(f[u][i], max(x, y)); 
        }
        for (int i = f[v].size() - 1; i >= 0; i--) {
            if (i + 1 < f[u].size()) {
                f[u][i] = max(f[u][i], f[u][i + 1]); 
            }
        }

		f[v].clear(); 
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> k;
	for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        p++; 
        g[p].pb(i);
        g[i].pb(p); 
	}
    k--; 
	dfs(1, 0);
	cout << f[1][0]; 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...