CFR 697 C. Lorenzo Von Matterhorn ( Tree Ad hoc )

Problem - C - Codeforces
Well, I came up with an algorithm to look at every previous operations in each operation, and splitting bifurcating paths into two unique paths. That gave me a TLE though I believe is good to go in terms of time complexity. Anyways, silly I did not figure out that having std::map to simply simulate will be fine, since there are only at most 64 * 1000 nodes to be used.

void solve(){
    int Q; cin >> Q;
    map< ll, ll > cost;
    while( Q-- ){
        int op; cin >> op;
        if( op == 1 ){
            ll u, v, w; cin >> u >> v >> w;
            while( u != v ){
                if( not ( u > v ) )
                    swap( u, v );
                cost[ u ] += w;
                u >>= 1LL;
            }
        } else{
            ll u, v; cin >> u >> v;
            ll ans = 0;
            while( u != v ){
                if( not ( u > v ) )
                    swap( u, v );
                if( cost.count( u ) )
                    ans += cost[ u ];
                u >>= 1;
            }
            cout << ans << "\n";
        }
    }
}

// TLE
vi int_to_bin( ll x ){
    vi res;
    stack< int > stk;
    while( x > 0 )
        stk.push( x & 1LL ),
        x >>= 1LL;
    while( not stk.empty() )
        res.push_back( stk.top() ),
        stk.pop();
    return res;
}

vi common_prefix( const vi &a, const vi &b ){
    vi res;
    for( int i = 0; i < a.size() and i < b.size(); ++i ){
        if( a[ i ] != b[ i ] ) return res;
        res.push_back( a[ i ] );
    }
    return res;
}

ll bin_to_int( const vi &v ){
    ll res = 0;
    for( int i = 0; i < v.size(); ++i )
        res = res * 2 + v[ i ];
    return res;
}

void show_bin( const vi &a ){
    for( int z : a )
        cout << z;
    cout << "\n";
}

void dfs( const vi &a, const vi &b, const vi &x, const vi &y, int &res, int k ){
    if( a == b ) return;
    if( x == y ) return;
    vi path = x; path.push_back( y[ x.size() ] );
    if( path.size() > b.size() ) return;
    if( path.size() <= a.size() ) return dfs( a, b, path, y, res, k );
    if( path.size() == a.size() and common_prefix( path, a ) != a ) return;
    while( k < path.size() ){
        if( path[ k ] != b[ k ] ) return;
        ++k;
    }
    dfs( a, b, path, y, ++res, k );
}

int get_count( const vi &a, const vi &b, const vi &x, const vi &y ){
    int res = 0;
    dfs( a, b, x, y, res, 0 );
    return res;
}

void solve(){
    int Q; cin >> Q;
    vector< tri > vop;
    for( int i = 0; i < Q; ++i ){
        int op; cin >> op;
        if( op == 1 ){
            ll u, v, w; cin >> u >> v >> w;
            if( not ( u < v ) ) swap( u, v );
            vi u_bin = int_to_bin( u );
            vi v_bin = int_to_bin( v );
            vi anc_bin = common_prefix( u_bin, v_bin );
            if( anc_bin != u_bin ) vop.push_back( tri( anc_bin, pair< vi, ll >( u_bin, w ) ) );
            if( anc_bin != v_bin ) vop.push_back( tri( anc_bin, pair< vi, ll >( v_bin, w ) ) );
        } else{
            ll u, v; cin >> u >> v;
            if( not ( u < v ) ) swap( u, v );
            vi u_bin = int_to_bin( u );
            vi v_bin = int_to_bin( v );
            vi anc_bin = common_prefix( u_bin, v_bin );
            ll res = 0;
            for( int j = 0; j < vop.size(); ++j ){
                vi x_bin = vop[ j ].tr1;
                vi y_bin = vop[ j ].tr2;
                vi z_bin = common_prefix( x_bin, y_bin );
                // show_bin( x_bin ), show_bin( y_bin ), show_bin( z_bin );
                int w = vop[ j ].tr3;
                res += 1LL * get_count( anc_bin, u_bin, z_bin, x_bin ) * w;
                res += 1LL * get_count( anc_bin, v_bin, z_bin, y_bin ) * w;
                res += 1LL * get_count( anc_bin, u_bin, z_bin, y_bin ) * w;
                res += 1LL * get_count( anc_bin, v_bin, z_bin, x_bin ) * w;
            }
            cout << res << "\n";
        }
    }
}