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

木の深いところから順に見ていく。

すべての人のやる気が負の時のコーナーケースに注意

計算量O(N).

int n;
int d[100003][2];
int ans[100003];
int ho=0;
int main(){

	scanf("%d",&n);
	ho = 0;
	int m = -100000000;
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&d[i][0],&d[i][1]);
		m = max(m,d[i][1]);
	}
	if(m < 0){
		printf("%d\n",m);
		return 0;
	}
	for(int i = n;i >= 1;i--){
		ho = max(ho,ans[i]+d[i][1]);
		ans[d[i][0]] += max(0,ans[i]+d[i][1]);
	}

	printf("%d\n",max(ho,ans[0]));

	return 0;
}