# Codeforces Round #362 (Div. 2) C. Lorenzo Von Matterhorn

,

http://codeforces.com/contest/697/problem/C

## problem

• 頂点$v, u$を結ぶ唯一の道上の辺の重みを$w$増加させる。
• 頂点$v, u$を結ぶ唯一の道上の辺の重みの総和を出力する。

## solution

Simply implement it. $O(q (\log v + \log u))$.

The tree depth is not large, at most $\log 10^{18} \approx 60$. So the number of involved vertices is bounded $q \cdot 2 \cdot 60 \le 120000$. This is a small number, so the naive implementation can be enough.

## implementation

#include <cstdio>
#include <unordered_map>
#include <functional>
typedef long long ll;
using namespace std;
void query(ll a, ll b, function<void (ll)> cont) {
if (a < b) {
cont(b);
query(a, b/2, cont);
} else if (a > b) {
cont(a);
query(a/2, b, cont);
}
}
int main() {
unordered_map<ll,ll> fee;
int q; scanf("%d", &q);
while (q --) {
int t; scanf("%d", &t);
if (t == 1) {
ll a, b, c;
scanf("%I64d%I64d%I64d", &a, &b, &c);
query(a, b, [&](ll i) { fee[i] += c; });
} else if (t == 2) {
ll a, b;
scanf("%I64d%I64d", &a, &b);
ll c = 0;
query(a, b, [&](ll i) { c += fee[i]; });
printf("%I64d\n", c);
}
}
return 0;
}