题目

在$Bytemountains$有N座山峰，每座山峰有他的高度$h_i$。有些山峰之间有双向道路相连，共$M$条路径，每条路径有一个困难值，这个值越大表示越难走，现在有$Q$组询问，每组询问询问从点v开始只经过困难值小于等于$x$的路径所能到达的山峰中第$k$高的山峰，如果无解输出$-1$。

思路

首先打开题解$kruskal重构树$+$主席树$？告辞。但是发现不是在线询问，好像可以苟一苟，思考下离线做法。对于每个询问，按照困难值排序，并顺次放入小于困难值的边貌似就可以解决只经过困难值小于等于$x$的路径所能到达的山峰这一条件了，那么第k大用权值线段树合并或者平衡树合并就可以搞定了。但是常 数 过 大以至于我(人丑常数大)只能开O2过，太屑了。

代码

#include<bits/stdc++.h>
#define Maxn 200005
#define Maxm 1000005
using namespace std;
int id=0,n,m,q,rt[Maxn],fa[Maxn],h[Maxn],p=1,size[Maxn];
struct edge{int u,v,w;}x[Maxm];
struct question{int v,x,k,id,ans;}Q[Maxm];
struct seg{int ls,rs,sum;}tree[Maxn*20];
bool cmp1(edge a,edge b){return a.w<b.w;}
bool cmp2(question a,question b){return a.x<b.x;}
bool cmp3(question a,question b){return a.id<b.id;}
inline void read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
inline void insert(int &root,int l,int r,int x)
{
    if (!root) root=++id;
    if (l==r) {tree[root].sum++;return;}
    int mid=l+r>>1;
    if (x<=mid) insert(tree[root].ls,l,mid,x);
    else insert(tree[root].rs,mid+1,r,x);
    tree[root].sum=tree[tree[root].ls].sum+tree[tree[root].rs].sum;
} 
inline int getfa(int x){if (fa[x]==x) return x;else return fa[x]=getfa(fa[x]);}
inline int merge(int x,int y,int l,int r)
{
    if (!x||!y) return x|y;
    if (l==r) {tree[x].sum+=tree[y].sum;return x;}
    int mid=l+r>>1;
    tree[x].ls=merge(tree[x].ls,tree[y].ls,l,mid);
    tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,r);
    tree[x].sum=tree[tree[x].ls].sum+tree[tree[x].rs].sum;
    return x;
}
inline int query(int root,int l,int r,int k)
{
    if (l==r) return l;
    int mid=l+r>>1;
    if (tree[tree[root].ls].sum>=k) return query(tree[root].ls,l,mid,k);
    else return query(tree[root].rs,mid+1,r,k-tree[tree[root].ls].sum);
}
int main()
{
    read(n),read(m),read(q);
    for (int i=1;i<=n;i++) read(h[i]),insert(rt[i],1,1e9,h[i]),fa[i]=i,size[i]=1;
    for (int i=1;i<=m;i++) read(x[i].u),read(x[i].v),read(x[i].w);
    sort(x+1,x+m+1,cmp1);
    for (int i=1;i<=q;i++) read(Q[i].v),read(Q[i].x),read(Q[i].k),Q[i].id=i;
    sort(Q+1,Q+q+1,cmp2);
    for (int i=1;i<=q;i++)
    {
        while (x[p].w<=Q[i].x&&p<=m)
        {
            int fx=getfa(x[p].u),fy=getfa(x[p].v);
            if (fx==fy) {p++;continue;}
            fa[fy]=fx;
            size[fx]+=size[fy];
            rt[fx]=merge(rt[fx],rt[fy],1,1e9);
            p++;
        }
        int fz=getfa(Q[i].v);
        if (size[fz]<Q[i].k) Q[i].ans=-1;else Q[i].ans=query(rt[fz],1,1e9,size[fz]-Q[i].k+1);
    }
    sort(Q+1,Q+q+1,cmp3);
    for (int i=1;i<=q;i++) cout<<Q[i].ans<<endl;
    return 0;
}