제출 #986765

#제출 시각아이디문제언어결과실행 시간메모리
986765Jawad_Akbar_JJCat in a tree (BOI17_catinatree)C++17
51 / 100
20 ms15448 KiB
#include <iostream>
#include <vector>

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

void dfs(int u){
	dp[u][0] = 1;
	for (int i : nei[u]){
		dfs(i);

		for (int i=0;i<=n;i++)
			temp[i] = 0;

		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);
			temp[k] = max(temp[k],dp[i][d-1] + mx);
		}
		mx = 0;
		for (int d = 1;d<=D;d++)
			temp[d] = max(temp[d],dp[i][d-1]);
		
		for (int d=n;d + d >= D;d--){
			mx = max(mx,dp[u][d]);
			temp[d] = max(temp[d],mx + dp[i][d-1]);
		}

		for (int j=n;j>=0;j--){
			dp[u][j] = max(dp[u][j],temp[j]);
			dp[u][j] = max(dp[u][j],dp[u][j+1]);
		}
	}
}

int main(){
	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...