TopCoderOpen 2017 Pittsburgh Hard RewardOnATree

Mediumの方が手間取ったかも。
(URL掲載待ち)

問題

根付き木を成すN頂点の無向グラフがある。
各頂点vには報酬R[v]が設定されている。

根を始点として頂点群を辿る。
その際次の条件を満たす頂点に任意に移動できるとする。

• 辺でつながった隣接点
• 高さが同じ点

経由した頂点における報酬の総和の最大値を求めよ。
各頂点は複数回経由してもよいが、報酬は1回しか得られない。

解法

同じ高さは任意に移動できるので、下の頂点に降りる段階で同じ高さにおける必要な頂点はすべて経由することができる。
よって下から上に上がることは考えない。

ある高さまで降りたとき、その高さにある報酬が正の頂点はすべて回るのが最適であるのは明らかである。
ただ、下の高さに降りるために報酬が負の点も経由すべき場合がある。
逆に降りるとき以外に報酬が負の点を経由すべき必要はない。
この考察をもとにDPで解こう。

以下各f(v)を求めればその最大値が解である。
f(v) := 最後にvで終わるような移動経路の報酬の総和の最大値

vと同じ高さに降り立つとき、最初に頂点wに降り立ったと考える。
すると f(v) = max(f(parent(w)+(v,w,および報酬が正の頂点の報酬の総和)) となる。
各高さにおいて「報酬が正の頂点の報酬の総和」を前処理で求めておけば、f(v)をすべて求める処理はO(N^2)で済む。

int N;
int P[2020],R[2020];

int D[2020];
vector<int> DV[2020];
int ET[2020];
int S[2020];

class RewardOnATree {
	public:
	int collect(vector <int> parent, vector <int> reward) {
		N=parent.size()+1;
		int i;
		FOR(i,N) DV[i].clear(),ET[i]=0,R[i]=reward[i];
		
		FOR(i,N-1) {
			P[i+1]=parent[i];
			D[i+1]=D[P[i+1]]+1;
			DV[D[i+1]].push_back(i+1);
			if(R[i+1]>=0) ET[D[i+1]]+=R[i+1];
		}
		
		int ma=S[0]=ET[0]=R[0];
		for(int d=1;d<N;d++) if(DV[d].size()) {
			FORR(b,DV[d]) {
				S[b]=-1<<30;
				FORR(a,DV[d]) if(a!=b) S[b]=max(S[b],S[P[a]]+ET[d]+min(0,R[a])+min(0,R[b]));
				S[b]=max(S[b],S[P[b]]+ET[d]+min(0,R[b]));
				ma=max(ma,S[b]);
			}
		}
		
		return ma;
		
	}
}

まとめ

600ptと900ptってしばしば難易度が逆転するな。