题目链接

Kruskal 重构树+主席树求调，变量名易懂，码风良好

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=5e5+5;
int n,m,q,cnt,len,hlen,id;
int h[N<<1],bcj[N<<1],kr[N<<1],fa[N<<1][25],lf[N<<1],L[N<<1],R[N<<1];
struct edge{
	int u,v,w;
}e[M];
vector<int> kg[N<<1]; 
bool cmp(edge a,edge b){ return a.w<b.w;}
int find(int x)
{
	if(bcj[x]==x) return x;
	else return bcj[x]=find(bcj[x]);
}
void kruskal()
{
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<n*2;i++) bcj[i]=i;
	cnt=n; 
	for(int i=1;i<=m;i++)
	{
		int rx=find(e[i].u),ry=find(e[i].v);
		if(rx==ry) continue;
		kr[++cnt]=e[i].w;
		kg[cnt].push_back(rx);
		kg[cnt].push_back(ry);
		bcj[rx]=bcj[ry]=cnt;
	} 
}
void dfs(int u,int las)
{
	fa[u][0]=las; 
	for(int i=1;i<=20;i++)
		fa[u][i]=fa[fa[u][i-1]][i-1]; 
	for(int i=0;i<kg[u].size();i++)
	{
		int v=kg[u][i];
		if(v==las) continue;
		dfs(v,u);
		L[u]=min(L[u],L[v]);
		R[u]=max(R[u],R[v]);
	}
	if(!kg[u].size()) 
		lf[++len]=u,L[u]=R[u]=len;
}
struct node{
	int ls,rs,val;
}tr[N<<5];
int rt[N<<1],a[N<<1];
int get_id(int x){ return lower_bound(h+1,h+1+hlen,x)-h; }
int get_root(int s,int lim)
{
	for(int i=20;i>=0;i--)
		if(kr[fa[s][i]]<=lim&&fa[s][i]>0) s=fa[s][i];
	return s;
}
int update(int p,int l,int r,int x)
{
	int k=++id;
	tr[k]=tr[p];
	if(l==r)
	{
		tr[k].val++;
		return k;
	} 
	int mid=(l+r)>>1;
	if(x<=mid) tr[k].ls=update(tr[p].ls,l,mid,x);
	else tr[k].rs=update(tr[p].rs,mid+1,r,x);
	tr[k].val=tr[tr[k].ls].val+tr[tr[k].rs].val;
	return k;
}
int query(int x,int y,int l,int r,int k)
{
	if(l==r) return (k-(tr[y].val-tr[x].val)==0?l:0);
	int mid=(l+r)>>1;
	int t=tr[tr[y].ls].val-tr[tr[x].ls].val;
	if(t>=k) return query(tr[x].ls,tr[y].ls,l,mid,k);
	else return query(tr[x].rs,tr[y].rs,mid+1,r,k-t);
}
void check()
{
	cout<<"Len: ";
	for(int i=1;i<=len;i++) cout<<lf[i]<<" "; puts("");
	for(int i=1;i<=cnt;i++)
		if(i>n) cout<<i<<" "<<kr[i]<<" "<<kg[i][0]<<" "<<kg[i][1]<<" "<<L[i]<<" "<<R[i]<<endl;
		else cout<<i<<" "<<kr[i]<<" "<<L[i]<<" "<<R[i]<<endl;
	puts("");
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),h[i]=a[i];
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	kruskal();
	for(int i=1;i<=cnt;i++) L[i]=1e9,R[i]=-1;
	dfs(cnt,0);
	sort(h+1,h+1+n);
	hlen=unique(h+1,h+1+n)-h-1;
//	check();
	for(int i=1;i<=len;i++)
		rt[i]=update(rt[i-1],1,hlen,get_id(h[lf[i]])); //重构树最底层序列 
	int st,lim,k; h[0]=-1;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d",&st,&lim,&k);
		int x=get_root(st,lim),th=R[x]-L[x]+2-k;
		int pos=query(rt[L[x]-1],rt[R[x]],1,hlen,th);
		printf("%d\n",h[pos]);
	}
	return 0;
}