ABC 040 D - 道路の老朽化対策について ( Union Find )

D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder
最初はパッとしなっかったけど、よく考えると、年について、クエリと辺をソートすると Union Find の問題になる。
Union Find 系の特徴はやはりこういう者だなと思った。
破壊を逆から見て構築にしたり、順番がバラバラな者をソートして一方に増えるものにするなど。
大きい年から小さい年へクエリを処理する。その年より大きい辺をいれる。Union Find で size も記録する。

typedef int T_triplet;
struct triplet{
    T_triplet first, second, third;
    triplet(){}
    triplet( T_triplet _f, T_triplet _s, T_triplet _t ){
        first = _f, second = _s, third = _t;
    }
    bool operator < ( const triplet &oth ) const{
        if( first != oth.first ) return first < oth.first;
        if( second != oth.second ) return second < oth.second;
        return third < oth.third;
    }
};
 
struct UnionFind{
    vi fa, size;
    UnionFind( int sz ){
        fa.resize( sz );
        size.resize( sz );
        for( int i = 0; i < sz; ++i )
            fa[ i ] = i,
            size[ i ] = 1;
    }
    int find( int x ){
        return fa[ x ] == x ? x : 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;
        size[ b ] += size[ a ];
        fa[ a ] = b; return true;
    }
};
 
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXY = 2e5 + 5;
const int MAXQ = 1e5 + 5;
const int MAXW = 2e5 + 5;
 
int N, M;
triplet edge[ MAXM ];
int Q;
triplet qry[ MAXQ ];
 
void solve(){
    cin >> N >> M;
    for( int i = 0; i < M; ++i ){
        cin >> edge[ i ].second >> edge[ i ].third >> edge[ i ].first;
        --edge[ i ].second;
        --edge[ i ].third;
    }
    priority_queue< triplet > pq;
    for( int i = 0; i < M; ++i )
        pq.push( edge[ i ] );
 
    cin >> Q;
    for( int i = 0; i < Q; ++i ){
        int u, y; cin >> u >> y;
        --u;
        qry[ i ] = triplet( y, u, i );
    }
    sort( qry, qry + Q );
 
    UnionFind uf = UnionFind( N );
 
    vi ans( Q );
    for( int i = Q - 1; i >= 0; --i ){
        while( !pq.empty() and pq.top().first > qry[ i ].first ){
            uf.unite( pq.top().second, pq.top().third );
            pq.pop();
        }
        ans[ qry[ i ].third ] = uf.size[ uf.find( qry[ i ].second ) ];
    }
 
    for( int i = 0; i < Q; ++i )
        cout << ans[ i ] << endl;
}