天下一プログラマーコンテスト2016予選A B - PackDrop (300)

B - PackDrop

概要

頂点番号が0～N-1である、N頂点の根付き木がある。根は頂点0。また葉がM個あり、i番目の葉の頂点番号をBiとする。
各辺に機器を置いてゆくことを考える。このとき根0から葉Biの間の辺には機器が合計でCi個あるようにし、かつ各辺に置く機器数の合計を最小化したい。各辺に置く機器数の最小値を答えよ。

制約

2 ≦ N ≦ 1000
1 ≦ Ci ≦ 100000

方針

根に近い辺に機器をたくさん置くと機器数が節約できる。ただし、最終的に葉が必要とする機器数にうまく収まるようにしないといけない。

具体的には葉から下記のステップで各頂点で必要な機器数を集計する。（解答ではdpという配列に格納する）
・葉は対応するCiを保持する
・葉でない頂点は、その頂点を根とする部分木について子が必要な機器数の最小値を保持する
・根は0を保持する

あとは各辺に割り当てる機器数を決定する。これは親xと子yを結ぶ辺であれば、dp[y] - dp[x]になる。

解答

Submission #6762033 - 天下一プログラマーコンテスト2016予選A

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int N, M;
 
vector<vector<int>> g;
map<int, int> mp;
 
vector<int> dp;
 
ll ans;
 
int dfs1(int x){
 
	if((int)g[x].size() == 0){
		return dp[x] = mp[x];
	}
 
	int mn = 1e8;
	for(int y : g[x]){
		mn = min(mn, dfs1(y));
	}
 
	return dp[x] = mn;
}
 
void dfs2(int x){
	for(int y : g[x]){
		dfs2(y);
		ans += dp[y] - dp[x];
	}
}
 
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N >> M;
 
	g.resize(N, vector<int>());
	rep(i, N-1){
		int p;
		cin >> p;
		g[p].push_back(i+1);
	}
 
	rep(i, M){
		int b, c;
		cin >> b >> c;
		mp[b] = c;
	}
 
	dp.resize(N, 0);
 
	dfs1(0);
	dp[0] = 0;
 
	// rep(i, N) cout << dp[i] << (i == N - 1 ? "\n" : ",");
 
	ans = 0;
	dfs2(0);
 
	cout << ans << endl;
}