PackDrop [天下一プログラマーコンテスト2016予選A : B]

問題

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualB_a

N頂点の木がある。
根は頂点0。
この木に対して、辺にコストをつける。
M個の葉について、根から葉までのパスの辺のコストの総和が指定されている。
このとき、辺につけるコストの総和の最小値は？

2 <= N <= 10^3
1 <= M <= N-1
1 <= Ci <= 10^5

考察

1. 辺のコストの総和が最小になる時はどういう時か考えてみる
2. 問題の例2を見て考えると割とすぐ出てくる

頂点2と頂点4はそれぞれパスの総和が5,7となれば良い。
0 -> 1 -> 2
0 -> 1 -> 4
とどちらも0->1の辺を用いているので、なるべく0->1の辺でコストが足されれば、総和は少なくなりそう。

3. つまり、各葉へのパスで共有している辺になるべくコストを集めれば良いことが分かる
4. これをうまいこと実装する手立てを考える
5. 木の問題(特にむっちゃ難しいって場面じゃないとき)はDFSで解く場合が多いです（体感）
6. とりあえずDFSで考えてみましょう

7. まず各頂点について最大限に流した時のコストを求めます -> dfs()
8. 後は頂点の差がその間の辺のコストとなるので、それを全部求めて足すだけです -> dfs2()

実装

http://tenka1-2016-quala.contest.atcoder.jp/submissions/822015

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
 
int N, M;
vector<int> child[1010];
int BC[1010];
//-----------------------------------------------------------------
#define INF INT_MAX/2
int dfs(int i) {
	if (0 < BC[i]) return BC[i];
 
	int _min = INF;
	for (int j : child[i]) _min = min(_min, dfs(j));
	BC[i] = _min;
 
	return _min;
}
//-----------------------------------------------------------------
typedef long long ll;
ll ans = 0;
void dfs2(int i) {
	for (int j : child[i]) {
		dfs2(j);
		ans += BC[j] - BC[i];
	}
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> M;
	rep(i, 1, N) {
		int P; cin >> P;
		child[P].push_back(i);
	}
 
	rep(i, 0, M) {
		int B, C; cin >> B >> C;
		BC[B] = C;
	}
 
	dfs(0);
	BC[0] = 0;
	dfs2(0);
 
	cout << ans << endl;
}