Codeforces 68 D. Half-decay tree - simezi

問題

高さhの完全二分木がある。これに対してq個の次のようなクエリに答えよ。

add v e 頂点vにeの電荷を加える
decay 木のdecay（後述）を求める。

木のdecayとは、次のようにして計算される値である。
木の葉をランダムに一つ選ぶ。木の根から、その葉までのパスに含まれる全ての辺を取り除く。
連結成分ごとに、電荷の和を取り、その最大値の期待値を求める。

制約条件

h≦30
-1000≦e≦1000

方針

http://mofupp.info/pukiwiki/?Codeforces%2FBetaRound62%2F62D
ここに解説があったので参考にした。

全てのノードvについて、vを根とする部分木に含まれる電荷の量を持っておく。
配列で取ると取れないので、mapなどで持つ。

vを根とする部分木vについて、他の部分のmax(lowerとする)が決まっているときの期待値を
rec(v,lower)とすると、

sum[v]≦lowerのときはlower
vが葉のときはmax(sum[v],lower)
そうでないときは、枝の選び方が2通りある。期待値は、(左の枝を選んだ場合の期待値+右の枝を選んだ場合の期待値)/2

左右の枝を選んだときの期待値はどう求めるかというと、
vからv1につながる枝を選んだ場合、
木はv1以下の部分木とその他の部分に分かれる。
v1以下の期待値は、lowerをmax(lower,sum[v]-sum[v1])として再帰的に求めればよい。

再帰のうち片方は、
sum[v]-sum[v1]≧sum[v2]が成り立つので、すぐにreturnして、
計算量は木の深さくらいしかかからない。

ソースコード

map<int,int> sum;
int h,q;
double rec(int v,double lower){
	if(sum[v]<=lower)return lower;
	if(v>=(1<<h))return max(sum[v]*1.0,lower);
	double res;
	res=rec(v*2,max(lower,sum[v]-sum[v*2]*1.0))+
		rec(v*2+1,max(lower,sum[v]-sum[v*2+1]*1.0));
	return res/2;
}
void run()
{
	cin>>h>>q;
	rep(i,q){
		string op; cin>>op;
		if(op=="add"){
			int v,e; cin>>v>>e;
			for(;v;v/=2)sum[v]+=e;
		}
		else printf("%.9f\n",rec(1,0));
	}
}