第7回日本情報オリンピック 春合宿 1日目 問題1 「委員会」 (Committee)

なんか前解いたことある気がする。

解法：DP

コーナーケースがある。

#include <bits/stdc++.h>

using namespace std;
const int INF = 100000000;
int n,ans=-INF,sa[100004][2],am=-INF,dp[100003];
int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)scanf("%d%d",&sa[i][0],&sa[i][1]),am=max(am,sa[i][1]);
	if(am < 0){printf("%d\n",am);
	}else{
	for(int i = n;i >= 1;i--){
		dp[i] = max(0,dp[i]+sa[i][1]);
		if(dp[i] > 0)dp[sa[i][0]] += dp[i];
		ans = max(ans,dp[i]);
	}
	ans = max(ans,dp[0]);
	printf("%d\n",ans);
	}
	return 0;
}