Google Code Jam 2022 Qualification Round : D. Chain Reactions

ちょっと手間取った。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a45ef7

問題

複数の根を持つ根付き木が与えられる。
各点にはポイントが設定されている。

葉を一つ指定すると、葉から根までにたどる頂点のうち、最大ポイントの分のポイントが得られる。
ただし、この時たどった全頂点のポイントは0になる。
任意の順で葉を選んだ時、総取得ポイントの最大値を求めよ。

解法

各頂点vについて、そのSubtree内の葉を選択したとき、そのうち1つの葉に対して、頂点vまたはその祖先をたどることでより大きなポイント得られる可能性がある。
言い換えれば、複数の子頂点を持つ場合、1つを除くと頂点vまたはその祖先のポイントを得られる可能性はない。

そこで、各頂点vでそのvのSubTreeの葉から得られるポイントのうち、未確定ポイントを1つだけ算出しよう。
子頂点が複数あるとき、未確定ポイントのうち最小値以外のものはその時点で取得ポイントが確定する。
最小値については、頂点vのポイントと比較し、大きな方のポイントをえられると考える。

int N;
int F[101010];
int P[101010];
vector<int> M[101010];
void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N+1) {
		M[i].clear();
	}
	FOR(i,N) {
		cin>>F[i+1];
	}
	FOR(i,N) {
		cin>>P[i+1];
	}
	ll ret=0;
	for(i=N;i>=1;i--) {
		if(M[i].empty()) {
			M[i].push_back(0);
		}
		sort(ALL(M[i]));
		FOR(j,M[i].size()) {
			if(j==0) M[P[i]].push_back(max(M[i][0],F[i]));
			else ret+=M[i][j];
		}
	}
	
	FORR(a,M[0]) ret+=a;
	
	cout<<"Case #"<<_loop<<": "<<ret<<endl;
}

まとめ

最初違うアプローチで1WAしてしまった。