P4197

经检测 只有线段树部分错了

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=5e5+5,V=1e9;
struct edge{
    int u,v,w;
}e[M];
int operator<(edge x,edge y){
    return x.w<y.w;
}
int n,m,T,a[N];
struct dsu{
    int p[N];
    dsu(){
        for(int i=1;i<=2*n;i++){
            p[i]=i;
        }
    }
    int find(int x){
        if(p[x]==x){
            return x;
        }
        return p[x]=find(p[x]);
    }
    void merge(int u,int v){
        p[u]=v;
    }
};
struct segtree{
    struct node{
        int l,r,siz;
        node(){
            l=r=siz=0;
        }
    }t[N*30];
    int node,root[N];
    segtree(){
        node=0;
    }
    void pushup(int u){
        t[u].siz=t[t[u].l].siz+t[t[u].r].siz;
    }
    map<int,vector<int>>mp;
    void build(int &u,int l,int r){
        u=++node;
        if(l==r){
            return;
        }
        int mid=(l+r)>>1;
        build(t[u].l,l,mid),build(t[u].r,mid+1,r);
    }
    void clone(int &u){
        t[++node]=t[u],u=node;
    }
    void init(){
        build(root[0],1,2*n);
    }
    void update(int &u,int l,int r,int x){
        clone(u);
        if(l==r){
            t[u].siz++;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            update(t[u].l,l,mid,x);
        }
        else{
            update(t[u].r,mid+1,r,x);
        }
        pushup(u);
    }
    void insert(int x,int mean,int val,int id){
        if(!mean){
            root[x]=root[x-1];
        }
        else{
            mp[val].push_back(id),root[x]=root[x-1],update(root[x],-V,V,val);
        }
    }
    int final(int A,int B){
        if(mp[A].size()<B){
            return -1;
        }
        return mp[A][B-1];
    }
    void Sort(){
        vector<int>vec;
        for(auto [A,B]:mp){
            sort(mp[A].begin(),mp[A].end()),reverse(mp[A].begin(),mp[A].end());
        }
    }
    pair<int,int>query(int u1,int u2,int l,int r,int k){
        if(l==r){
            return {l,k};
        }
        int mid=(l+r)>>1,num=t[t[u2].r].siz-t[t[u1].r].siz;
        if(num<=k){
            return query(t[u1].r,t[u2].r,mid+1,r,k);
        }
        return query(t[u1].l,t[u2].l,l,mid,k-num);
    }
    pair<int,int>kth(int l,int r,int k){
        return query(root[l-1],root[r],-V,V,k);
    }
}segtree;
struct kruscal{
    vector<int>g[N];
    int siz[N],dfn[N],rnk[N],stamp,val[N],f[N][20];
    kruscal(){
        for(int i=1;i<=2*n;i++){
            siz[i]=dfn[i]=rnk[i]=stamp=val[i]=0;
            for(int j=0;j<20;j++){
                f[i][j]=0;
            }
        }
    }
    void dfs(int u){
        siz[u]=1,dfn[u]=++stamp,rnk[stamp]=u;
        for(int v:g[u]){
            f[v][0]=u;
            for(int i=1;i<20;i++){
                f[v][i]=f[f[v][i-1]][i-1];
            }
            dfs(v),siz[u]+=siz[v];
        }
    }
    void build(){
        dsu dsu;
        int node=n;
        for(int i=1;i<=m;i++){
            if(dsu.find(e[i].u)!=dsu.find(e[i].v)){
                int u=dsu.find(e[i].u),v=dsu.find(e[i].v);
                node++,dsu.merge(u,node),dsu.merge(v,node),g[node].push_back(u),g[node].push_back(v),val[node]=e[i].w;
            }
        }
        for(int i=node;i>=1;i--){
            if(!dfn[i]){
                dfs(i);
            }
        }
        segtree.init();
        for(int i=1;i<=node;i++){
            segtree.insert(i,siz[rnk[i]]==1,val[rnk[i]],rnk[i]);
        }
        segtree.Sort();
    }
    int calc(int u,int x){
        for(int i=19;i>=0;i--){
            if(val[f[u][i]]<=x&&f[u][i]){
                u=f[u][i];
            }
        }
        if(val[u]>x){
            return -1;
        }
        return u;
    }
    int query(int u,int x,int k){
        u=calc(u,x);
        if(u==-1){
            return -1;
        }
        vector<pair<int,int>>vec;
        auto [A,B]=segtree.kth(dfn[u],dfn[u]+siz[u]-1,k);
        return segtree.final(A,B);
    }
}kruscal;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cin>>n>>m>>T;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1),kruscal.build();
    for(int u,x,k;T--;){
        cin>>u>>x>>k;
        int num=kruscal.query(u,x,k);
        if(num==-1){
            cout<<-1<<'\n';
        }
        else{
            cout<<a[num]<<'\n';
        }
    }
}