Codeforces #362 Div1 A. Lorenzo Von Matterhorn

一応赤復帰したけど、Cをしょうもないミスで落としたのは頂けない。
http://codeforces.com/contest/696/problem/A

問題

BFSの到達順にインクリメントされていくラベルを張った根付完全二分木を考える。
以下の２種のクエリを計Q個処理せよ。

• 3値U,V,wが与えられるので、ラベルU,Vに相当する最短経路上の頂点に値wを加算する。
• 2値U,Vが与えられるので、ラベルU,Vに相当する最短経路上の頂点の値の総和を答える。

解法

1回のクエリで通る頂点は高々O(logU+logV)個である。
X=LCA(U,V)とする。

前者のクエリに対しては、U→X及びV→Xに至る経路上の各頂点にmapを使って値を加算しよう。
後者も同様にU→X及びV→Xに至る経路上の各頂点の値の総和を取ればよい。

幸い今回は完全二分木なので、LCAは容易に求められる。

int Q;
map<ll,ll> M;
ll X,Y;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>Q;
	while(Q--) {
		cin>>i>>X>>Y;
		
		if(i==1) {
			cin>>x;
			while(X!=Y) {
				if(X<Y) M[Y] += x, Y/=2;
				if(X>Y) M[X] += x, X/=2;
			}
		}
		else {
			ll ret=0;
			while(X!=Y) {
				if(X<Y) ret += M[Y], Y/=2;
				if(X>Y) ret += M[X], X/=2;
			}
			cout<<ret<<endl;
		}
	}
	
}

まとめ

ここらへんはまだ簡単。