Submission #986739

#	Time	Username	Problem	Language	Result	Execution time	Memory
986739		Jawad_Akbar_JJ	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	1 ms	348 KiB

catinatree

#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

• Subtask 1: 0 / 11
• Subtask 2: 0 / 40
• Subtask 3: 0 / 49