本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-24 12:59:42

思路

首先，该题有求联通块，不妨使用并查集求两点是否在同一联通块并且进行合并操作。 $2$ 操作是求联通块内第 $k$ 大，我们可以使用set来操作，合并时进行启发式合并，求第 $k$ 大可以直接暴力求解。

代码

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void merge(int u,int v){
    u=find(u),v=find(v);
    if(u!=v){
        if(s[u].size()<s[v].size()){
            for(auto i:s[u]) s[v].insert(i);
        }
        else{
            for(auto i:s[v]) s[u].insert(i);
            swap(s[u],s[v]);
        }
        fa[u]=v;
    }
}


int query(int u,int k){
    u=find(u);
    if(s[u].size()<k) return -1;
    else{
        set<int> :: iterator it;
        for(it=s[u].begin();it!=s[u].end();it++){
            k--;
            if(k==0) return *it;
        }
    }
}