给出一个无向图,每条边有一个边权l,代表这条边的困难度.每个点有一个高度值h.

共有q组询问,每一个询问有三个参数v,x,k.表示从点v出发,在走过的边的困难值的最大值不超过x的情况下,所能到达的点的高度的第k大值是多少.

链接

洛谷4197

题解

按边权从小到大排序,建Kruskal重构树,在重构树上,从点v出发不断向上倍增,直到点权将要大于x时停止.此时,当前点的子树就是可以遍历到的所有点.在DFS序上建个主席树来实现区间k大查询即可.

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,q,i,cnt,tot;
int f[N],son[N][2],l[N],r[N],w[N],b[N],root[N],h[N],d[N];
int fa[N][20];

map <int,int> M;

struct Data{
    int x,y,l;
}a[N*4];

struct Tree{
    int l,r,d;
}t[N*64];

IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}

IL int read(){
    int p=0,f=1;    char    c=getchar();
    while (c<48||c>57)  {if (c=='-')    f=-1;   c=getchar();}
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p*f;
}

IL bool cmp(const Data &a,const Data &b){return (a.l<b.l);}

IL int Find(int x){return (x==f[x])?x:f[x]=Find(f[x]);}

IL int Build(int low,int high){
    int x=++tot,mid=(low+high)>>1;
    t[x].d=0;
    if (low==high)  return x;
    t[x].l=Build(low,mid);  t[x].r=Build(mid+1,high);
    return x;
}

IL int Insert(int pre,int low,int high,int val){
    int x=++tot,mid=(low+high)>>1;
    t[x]=t[pre];
    if (low==high)  {t[x].d++;  return x;}
    (val<=mid)?t[x].l=Insert(t[x].l,low,mid,val):t[x].r=Insert(t[x].r,mid+1,high,val);
    t[x].d=t[t[x].l].d+t[t[x].r].d;
    return x;
}

inline int Query(int l,int r,int low,int high,int p){
    int x=0,mid=(low+high)>>1;
    if (low==high) return low;
    x=t[t[r].l].d-t[t[l].l].d;
    if (p<=x)   return Query(t[l].l,t[r].l,low,mid,p);
    else return Query(t[l].r,t[r].r,mid+1,high,p-x);
}

IL void Dfs(int x){
    l[x]=w[0];
    if (!son[x][0]){
        r[x]=w[0]+1;
        w[++w[0]]=h[x]; return;
    }
    Dfs(son[x][0]); Dfs(son[x][1]);
    r[x]=w[0];
}

IL void Ready(){
    reg int i=0,sum=0,x=0,y=0,j=0;
    for (i=1;i<=(n<<1)+5;i++)   f[i]=i;
    cnt=n;
    for (i=1;i<=m;i++){
        x=Find(a[i].x); y=Find(a[i].y);
        if (x==y)   continue;
        ++sum;
        f[x]=f[y]=++cnt;
        fa[x][0]=fa[y][0]=cnt;
        son[cnt][0]=x;  son[cnt][1]=y;
        d[cnt]=a[i].l;
        if (sum>=n-1)   break;
    }
    Dfs(cnt);
    d[0]=INF;   tot=0;
    root[0]=Build(1,n);
    for (i=1;i<=n;i++)  root[i]=Insert(root[i-1],1,n,w[i]);
    for (j=1;j<=19;j++)
        for (i=1;i<cnt;i++)
            fa[i][j]=fa[fa[i][j-1]][j-1];
}

IL int Calc(int x,int y){
    reg int i=0;
    for (i=19;i>=0;i--)
        if (d[fa[x][i]]<=y) x=fa[x][i];
    return x;
}

IL void Work(){
    reg int v=0,x=0,k=0,p=0;
    while (q--){
        v=read();   x=read();   k=read();
        p=Calc(v,x);
        if (r[p]-l[p]<k)    {
            puts("-1"); continue;
        }
        printf("%d\n",b[Query(root[l[p]],root[r[p]],1,n,r[p]-l[p]+1-k)]);
    }
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();   q=read();
    for (i=1;i<=n;i++)  h[i]=b[i]=read();
    sort(b+1,b+1+n);
    M[b[1]]=++tot;
    for (i=2;i<=n;i++)
        if (b[i]!=b[i-1])   M[b[i]]=++tot;
    for (i=1;i<=n;i++)  h[i]=M[h[i]];
    for (auto j : M)    b[j.second]=j.first;

    for (i=1;i<=m;i++){
        a[i].x=read();  a[i].y=read();  a[i].l=read();
    }
    sort(a+1,a+1+m,cmp);
    Ready();    Work();
    return 0;
}