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

EはともかくDは解きたかった。
http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualB_a

問題

ネットワーク機器が根付き木を成すグラフ状に接続されている。
各辺に機械を１個取り付けると、その辺を介したネットワークパケットの到達率が0.99倍になる。
葉に相当する各機器vに到達すべきパケットの到達率が0.99^C[v]とするため、必要な機械の数の最小値を求めよ。

解法

0.99^C[v]とか考えると面倒だが、要は各葉vまで到達する経路の辺上に計C[v]個の機械を設置すればよい。

葉以外の各頂点vに対し根からvまでに何個の機械を置けばいいかを考えよう。
vの子頂点cに対するmin(C[c])を求めると、各子頂点はC[c]個以上の機械が必要なので、根からvまでにmin(C[c])個の機会を置くとよい。
よって(本来葉以外にC[v]は定義されないが)C[v]=min(C[c])としてしまおう。
するとvと各cの間にC[c]-C[v]個の機械を新たに設置すればよい。

上記処理を葉から順に行えばよい。
なお、根はそれ以上親側に機械を置けないことに注意。

int N,M;
int P[2020];
ll need[2020],tot[2020];
vector<int> E[2020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N-1) {
		cin>>P[i+1];
		E[P[i+1]].push_back(i+1);
	}
	FOR(i,M) {
		cin>>x>>y;
		need[x]=y;
	}
	
	ll ret=0;
	for(i=N-1;i>=0;i--) if(E[i].size()) {
		ll mi=1<<30;
		FORR(e,E[i]) mi=min(mi,need[e]);
		if(i==0) mi=0;
		FORR(e,E[i]) ret += need[e]-mi;
		need[i]=mi;
	}
	cout<<ret<<endl;
}

まとめ

実際に使われてるのか…。