两份一模一样的代码取得了不同的分数：

R120942709

R120942402

不知道是哪里 UB 了（

写的是离线并查集加 FHQTreap 合并。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <random>
#include <cmath>

using namespace std;
const int N=100100,M=500500;

int n,m,q,in1,in2,in3,tot;
int h[N],ans[M],fa[N];

std::mt19937 rng(std::random_device{}());

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

struct Edge{
    int u,v,w;
}e[M];

struct Query{
    int v,x,k,id;
}query[M];

bool cmp1(Edge a,Edge b){
    return a.w<b.w;
}

bool cmp2(Query a,Query b){
    return a.x<b.x;
}

struct FHQn{
    int ch[2],val,siz,key;
};
struct FHQ{
    FHQn a[N];
    void push_up(int p){
        a[p].siz=a[a[p].ch[0]].siz+a[a[p].ch[1]].siz+1;
    }
    int built(int k){
        int p=++tot;
        a[p]={{0,0},k,1,rng()};
        return p;
    }
    int merge(int p,int q){
        if(!p||!q) return p+q;
        if(a[p].key<a[q].key){
            a[p].ch[1]=merge(a[p].ch[1],q);
            push_up(p);return p;
        }
        else{
            a[q].ch[0]=merge(p,a[q].ch[0]);
            push_up(q);return q;
        }
    }
    void split(int p,int k,int &l,int &r){
        if(!p){l=r=0;return ;}
        if(a[p].val<=k){l=p;split(a[p].ch[1],k,a[p].ch[1],r);}
        else{r=p;split(a[p].ch[0],k,l,a[p].ch[0]);}
        push_up(p);
    }
    int kth(int p,int k){
        while(true){
            if(a[a[p].ch[1]].siz>=k) p=a[p].ch[1];
            else if(a[a[p].ch[1]].siz+1==k) return p;
            else k-=a[a[p].ch[1]].siz+1,p=a[p].ch[0];
        }
    }
    void insert(int &rt,int p){
        int x,y;
        split(rt,a[p].val,x,y);
        rt=merge(merge(x,p),y);
    }
    int find_num(int rt,int k){
        return a[kth(rt,k)].val;
    }
    void dfs(int x,int &y){
        if(!x) return ;
        dfs(a[x].ch[0],y);
        dfs(a[x].ch[1],y);
        a[x].ch[0]=a[x].ch[1]=0;
        insert(y,x);
    }
}tree;

int merge(int x,int y){
    if(tree.a[x].siz>tree.a[y].siz) swap(x,y);
    tree.dfs(x,y);return y;
}

void addedge(int id){
    int u=e[id].u,v=e[id].v;
    if(find(u)==find(v)) return ;
    int rt=merge(fa[u],fa[v]);
    fa[find(u)]=fa[find(v)]=rt;fa[rt]=rt;
}

int ask(int x,int k){
    if(tree.a[find(x)].siz<k) return -1;
    return tree.find_num(find(x),k);
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
        tree.built(h[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&in1,&in2,&in3);
        e[i]=Edge{in1,in2,in3};
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&in1,&in2,&in3);
        query[i]=Query{in1,in2,in3,i};
    }
    sort(e+1,e+m+1,cmp1);
    sort(query+1,query+q+1,cmp2);
    for(int i=1,j=0;i<=q;i++){
        while(j<m&&e[j+1].w<=query[i].x) addedge(++j);
        ans[query[i].id]=ask(query[i].v,query[i].k);
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}