697C - Lorenzo Von Matterhorn - CodeForces Solution

#include "bits/stdc++.h"
#include <cmath>
using namespace std;
#define EPS 1e-9
#define endl "\n"
#define clr(d,v) memset(d,v,sizeof(d))
#define ll long long
#define PI 3.1415926535
int dx[8] = {0,1,0,-1,1,-1,1,-1};
int dy[8] = {1,0,-1,0,1,1,-1,-1};
ll gcd(ll x, ll y) {return(!y) ? x : gcd(y, x%y);}
ll lcm(ll x, ll y) {return((x / gcd(x, y))*y);}
void fast();
const int N = 2e5 + 5;
ll mod = 1e9+7;
//--------------------------------------------------------
ll fact[25];
map<pair<ll, int>,ll> up;
map<pair<ll, ll>, ll> val;
//--------------------------------------------------------
ll get_lca(ll a, ll b){
    map<ll,bool> mp;
    while(a){
        mp[a] = 1;
        a = a / 2;
    }
    while(b){
        if(mp[b]) return b;
        b = b / 2;
    }
    return 1;
}

void update(ll node, ll lca, ll w){
    while(node != lca){
        val[{node / 2, node}] += w;
        node /= 2;
    }
}

ll get(ll node, ll lca){
    ll sum = 0;
    while(node != lca){
        sum += val[{node / 2,node}];
        node /= 2;
    }
    return sum;
}

//--------------------------------------------------------
int main(){
    
    fast();

    int q;
    cin >> q;
    set<ll> nodes;
    vector<pair<pair<ll, ll>, pair<ll, ll>>> vec;
    for(int i = 0 ; i < q ; i++){
        ll t,u,v,w=0;
        cin >> t;
        if(t==2) cin >> u >> v;
        else cin >> u >> v >> w;
        vec.push_back({{t,u},{v,w}});
        nodes.insert(u);
        nodes.insert(v);
    }
    

    
//
    for(int i = 0 ; i < vec.size() ; i++){
        ll t = vec[i].first.first;
        ll u = vec[i].first.second;
        ll v = vec[i].second.first;
        ll w = vec[i].second.second;
        ll lca = get_lca(u, v);
        if(t == 1){
            update(u,lca,w);
            update(v,lca,w);
        }
        else{
//            cout << lca  << endl;
           cout << get(u,lca) + get(v,lca)<< endl;
        }
//
//        for(int j = 1 ; j <= 10 ; j++){
//           // cout << j << "-" << val[j] << "   ";
//        }
//        cout << endl;
    }

    
    

    
    
}
//---------------------------------------------------------
    
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}