AGC D - Stamp Rally ( Parallel Binary Search OR Persistent Union-Find )

D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder
Finally found an easy problem to start familiarising with parallel binary search ( I thought it is called holistic binary search ).
pekempey.hatenablog.com
The link above really helped, and basically I am just copying.
For PBS, I understand that there are at most log M < 20 depths, so we will only need to have 20 UnionFind structures declared, and with help of DFS, we ensure that when we are at some block on some depth, e.g. depth = d and range = [ ql, qr ], the edges [ 0, ql ) are united already in uf[ d ]. I mean, I thought it will be ensured by the nature of DFS. However, it seems not and one has to record the last position of that uf[ d ], and manually unite from last_pos[ d ] to mid, to assure this, which I can't comprehend yet.
For PUF, 永続セグメント木で試みたが失敗した

WA や TLE や MLE だし、諦めるしかない。。これで解いた人もなかったらしい。
Here's a great CFR post that is also a good place to begin with. Can't wait to solve Meteors this time.

struct quad{
    int first, second, third, fourth;
    quad(){}
    quad( int _f, int _s, int _t, int _fo ){
        first = _f, second = _s, third = _s, fourth = _fo;
    }
    bool operator < ( const quad &oth ) const{
        if( first != oth.first ) return first < oth.first;
        if( second != oth.second ) return second < oth.second;
        if( third != oth.third ) return third < oth.third;
        return fourth < oth.fourth;
    }
};
 
struct UnionFind{
    vi fa, size;
    UnionFind( int sz = 0 ){
        fa.resize( sz );
        size.resize( sz );
        for( int i = 0; i < sz; ++i )
            fa[ i ] = i,
            size[ i ] = 1;
    }
    int find( int x ){
        if( fa[ x ] == x ) return x;
        return fa[ x ] = find( fa[ x ] );
    }
    bool same( int x, int y ){
        int a = find( x );
        int b = find( y );
        return a == b;
    }
    bool unite( int x, int y ){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b;
        size[ b ] += size[ a ];
        return true;
    }
} uf[ 20 ];
 
int pos[ 20 ];
 
int N, M;
vector< pii > edge;
 
void parallel_bs( int dpt, int ql, int qr, vector< quad > cur, vi &ans ){
    if( ql == qr ){
        for( auto q : cur )
            ans[ q.fourth ] = ql;
        return;
    }
    int mid = ql + qr >> 1;
    for( int &i = pos[ dpt ]; i <= mid; ++i )
        uf[ dpt ].unite( edge[ i ].first, edge[ i ].second );
    vector< quad > left, right;
    for( auto q : cur ){
        int a = uf[ dpt ].find( q.second );
        int b = uf[ dpt ].find( q.third );
        int size = uf[ dpt ].size[ a ] + uf[ dpt ].size[ b ];
        if( a == b ) size /= 2;
        if( size >= q.first ) left.push_back( q );
        else right.push_back( q );
    }
    parallel_bs( dpt + 1, ql, mid, left, ans );
    parallel_bs( dpt + 1, mid + 1, qr, right, ans );
}
 
void solve(){
    cin >> N >> M;
 
    edge = vector< pii >( M );
    for( int i = 0; i < M; ++i )
        cin >> edge[ i ].first >> edge[ i ].second,
        --edge[ i ].first, --edge[ i ].second;
 
    int Q; cin >> Q;
    vector< quad > qry( Q );
    for( int i = 0; i < Q; ++i )
        cin >> qry[ i ].second >> qry[ i ].third >> qry[ i ].first,
        --qry[ i ].second, --qry[ i ].third,
        qry[ i ].fourth = i;
 
    for( int i = 0; i < 20; ++i )
        uf[ i ] = UnionFind( N );
 
    vi ans( Q );
    parallel_bs( 0, 0, M - 1, qry, ans );
 
    for( int i = 0; i < Q; ++i )
        cout << ans[ i ] + 1 << "\n";
}

// persistent segment tree for persistent union find -> WA + TLE + MLE QQ
#include <bits/stdc++.h>
using namespace std;

typedef pair< int, int > pii;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< pii > vp;
typedef vector< vp > vvp;

const int MAXN = 1e5 + 1;
const int MAXM = 1e5 + 1;
const int MAXQ = 1e5 + 1;

const int MAXMEM = 4e6;

struct itvt_data{
    int fa, size;
    itvt_data( int _f = -1, int _s = 1 ): fa( _f ), size( _s ){}
};

struct itvt{
    static itvt mem[ MAXMEM ];
    int lb, rb;
    itvt_data data;
    itvt *lc, *rc;
    itvt(): lc( NULL ), rc( NULL ){}
    itvt( int _l, int _r, int _f ): lb( _l ), rb( _r ){
        data.fa = _f;
    }
    itvt_data get_data( int k ){ // returns fa, log( rb - lb )
        if( lb == rb ) return data;
        int mid = ( lb + rb ) / 2;
        if( k <= mid ) return lc->get_data( k );
        return rc->get_data( k );
    }
    void update( int k, const itvt_data &d ){
        if( lb == rb ) return ( void )( data = d );
        int mid = ( lb + rb ) / 2;
        if( k <= mid ) return lc->update( k, d );
        return rc->update( k, d );
    }
    int find( int x ){
        int fa_x = get_data( x ).fa;
        if( x == fa_x ) return x;
        update( x, itvt_data( fa_x, 0 ) );
        return fa_x;
    }
} itvt::mem[ MAXMEM ], *ptr = itvt::mem, *ver[ MAXM ];

itvt* build( int lb, int rb ){
    if( lb == rb ) return new ( ptr++ ) itvt( lb, rb, lb );
    int mid = ( lb + rb ) / 2;
    itvt *t = new ( ptr++ ) itvt( lb, rb, -1 );
    t->lc = build( lb, mid );
    t->rc = build( mid + 1, rb );
    return t;
}

itvt* clone( itvt *t ){
    itvt *res = new ( ptr++ ) itvt();
    res->lb = t->lb, res->rb = t->rb, res->data = t->data;
    res->lc = t->lc, res->rc = t->rc;
    return res;
}

itvt* modify( itvt *t, int k, const itvt_data &d ){
    itvt *res = clone( t );
    if( t->lb == t->rb ){
        res->data = d;
        return res;
    }
    int mid = ( t->lb + t->rb ) / 2;
    if( k <= mid ) res->lc = modify( t->lc, k, d );
    else res->rc = modify( t->rc, k, d );
    return res;
}

itvt* unite( itvt *t, int u, int v ){
    int a = t->find( u );
    int b = t->find( v );
    if( a == b ) return clone( t );
    int size_a = t->get_data( a ).size;
    int size_b = t->get_data( b ).size;
    itvt *res = modify( t, a, itvt_data( b, size_b ) );
    res = modify( res, b, itvt_data( b, size_a + size_b ) );
    // res->update( a, itvt_data( b, size_a ) );
    // res->update( b, itvt_data( b, size_a + size_b ) );
    return res;
}

void solve(){
    int N, M; cin >> N >> M;
    ver[ 0 ] = build( 0, N - 1 );

    for( int i = 1; i <= M; ++i ){
        int u, v; cin >> u >> v;
        --u, --v;
        ver[ i ] = unite( ver[ i - 1 ], u, v );
    }

    int Q; cin >> Q;
    for( int i = 0; i < Q; ++i ){
        int u, v, c; cin >> u >> v >> c;
        --u, --v;
        int lb = 1, rb = M, ans = -1;
        while( lb <= rb ){
            int mid = lb + rb >> 1;
            int a = ver[ mid ]->find( u );
            int b = ver[ mid ]->find( v );
            int size = ver[ mid ]->get_data( a ).size +
                       ver[ mid ]->get_data( b ).size;
            if( a == b ) size /= 2;
            if( size >= c ) ans = mid, rb = mid - 1;
            else lb = mid + 1;
        }
        cout << ans << "\n";
    }
}

int main(){
    ios::sync_with_stdio( false );
    solve();
    return 0;
}