Submission #986739

#TimeUsernameProblemLanguageResultExecution timeMemory
986739Jawad_Akbar_JJCat in a tree (BOI17_catinatree)C++17
0 / 100
1 ms348 KiB
#include <iostream>
#include <vector>

using namespace std;
const int N = 1501;
vector<int> nei[N];
int dp[N][N], D;

void dfs(int u){
	dp[u][0] = 1;
	for (int i : nei[u]){
		dfs(i);
		dp[i][D-1] = max(dp[i][D-1],dp[i][D]);
		int mx = 0;
		for (int d = 1;d<=D;d++){
			mx = max(mx,dp[u][D - d]);
			int k = min(d,D - d);
			dp[u][k] = max(dp[u][k],dp[i][d-1] + mx);
		}
		for (int d = 1;d<=D;d++)
			dp[u][d] = max(dp[u][d],dp[i][d-1]);
	}
}

int main(){
	int n;
	cin>>n>>D;

	for (int i=2;i<=n;i++){
		int p;
		cin>>p;
		nei[p + 1].push_back(i);
	}

	dfs(1);

	int ans = 0;

	for (int i=0;i<=n;i++)
		ans = max(ans,dp[1][i]);
	cout<<ans<<'\n';
}


// next
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...