TopCoder SRM 719 Div1 Medium OwaskiAndTree

妙に手間取った。
https://community.topcoder.com/stat?c=problem_statement&pm=14676

問題

木を成す無向グラフが与えられる。
各頂点vにはスコアS[v]が設定されている。S[v]は負の場合もある。

頂点0を始点とし、辺をたどり頂点群を通るすることを考える。
各頂点は何度通ってもよく、1度も通らなくてもよい。
初めて頂点を通るとき、自身のスコアにS[v]が加算される。
また、任意のタイミングで自身のスコアをリセットすることができる。

最適な訪問順およびリセットタイミングを取る場合、得られる総スコアの最大値を求めよ。

解法

各頂点の状態は、以下のいずれかである。
なお、下記状態は根から近い順に遷移する。

1. リセット前に通過済みなので、最終スコアに計上されない
2. リセット後に通過するので、最終スコアに計上される
3. 通過しないので最終スコアに計上されない

各頂点3つの可能性があることを考慮し、それぞれの状態に対応するSubTreeのスコア最大値をDFSで求めていこう

class OwaskiAndTree {
	public:
	int maximalScore(vector <int> parent, vector <int> pleasure) {
		int N=pleasure.size();
		pair<int,int> P[1010]={};
		
		for(int i=N-1;i>=1;i--) {
			P[i].second += pleasure[i];
			int p=parent[i-1];
			P[p].first+=max({P[i].first,P[i].second,0});
			P[p].second+=max({P[i].second,0});
		}
		
		return max({P[0].first, P[0].second+pleasure[0], 0});
	}
}

まとめ

本番何十行も書いたのに、整理したらこんな短くなっちゃった。