题目描述
(n)个点(m)条边的无向图，每个点和每条边都有一个权值，询问(u,x,k)：问从(u)开始走边权不超过(x)的边所能到达的点中第(k)大的权值
分析
毕竟是在克鲁斯卡尔重构树的博客里面找到这题的，那么必然是要用到克鲁斯卡尔重构树的喽
发现问题可以转化成求重构树上某一个点子树内的第(k)大，由于子树内的节点dfs序是连续的，可以用主席树来维护。
代码
细节还挺多的
注意数组，还有主席树新建节点的时候记得复制信息
#include<bits/stdc++.h>
#define rep(X,A,B) for(int X=A;X<=B;X++)
#define tep(X,A,B) for(int X=A;X>=B;X--)
#define LL long long
const int N=400010;
const int M=500010;
const int NN=400010;
const int NNN=5000010;
const int MX=30;
using namespace std;
struct nn{
int u,v,w;
}E[M];
int cmp(nn A,nn B){
return A.w<B.w;
}
int n,m,T;
int a[N],hlp[N],len;
int tmp=0,dfn[NN],pt[NN],lef[NN],rit[NN],val[NN];
int tot=0,son[NNN][2],fa[NN][MX],pa[NN],dep[NN];
int sum[NNN],rt[N];
void READ(){
int u,v,w;
scanf("%d%d%d",&n,&m,&T);
rep(i,1,n)scanf("%d",&a[i]),hlp[i]=a[i];
//---
sort(hlp+1,hlp+n+1);
len=unique(hlp+1,hlp+n+1)-hlp-1;
rep(i,1,n)a[i]=lower_bound(hlp+1,hlp+len+1,a[i])-hlp;
//---
rep(i,1,m){
scanf("%d%d%d",&u,&v,&w);
E[i]=(nn){u,v,w};
}
}//chked
struct SegmentTree{
void BUILD(int x,int l,int r){
sum[x]=0;
if(l==r)return;
int mid=(l+r)>>1;
son[x][0]=++tot;BUILD(son[x][0],l,mid);
son[x][1]=++tot;BUILD(son[x][1],mid+1,r);
}//chked
void INS(int x,int las,int l,int r,int pos){
if(l==r){
sum[x]=sum[las]+1;//一开始写成sum[x]++挂了好久
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
son[x][0]=++tot;son[x][1]=son[las][1];
INS(son[x][0],son[las][0],l,mid,pos);
}
else{
son[x][1]=++tot;son[x][0]=son[las][0];
INS(son[x][1],son[las][1],mid+1,r,pos);
}
sum[x]=sum[son[x][0]]+sum[son[x][1]];
}
int QUE(int x,int las,int l,int r,int pos){
if(pos<=0)return -1;
if(l==r)return hlp[l];
if(sum[x]-sum[las]<pos)return -1;
int mid=(l+r)>>1;
int lf=sum[son[x][0]]-sum[son[las][0]];
if(lf>=pos)return QUE(son[x][0],son[las][0],l,mid,pos);
return QUE(son[x][1],son[las][1],mid+1,r,pos-lf);
}
}sg;
int GETFA(int x){
if(x!=pa[x])pa[x]=GETFA(pa[x]);
return pa[x];
}
void SEARCH(int x){
if(!x)return;
if(x<=n){
pt[++tmp]=x,dfn[x]=tmp,lef[x]=rit[x]=tmp;
return;
}
SEARCH(son[x][0]);
SEARCH(son[x][1]);
lef[x]=lef[son[x][0]];
rit[x]=rit[son[x][1]];
}//chked
void CHKFA(){
SEARCH(tot);
dep[tot]=0;
tep(x,tot,1)dep[x]=dep[fa[x][0]]+1;
rep(i,1,20){
rep(x,1,tot){
if((1<<i)>=dep[x])continue;
fa[x][i]=fa[fa[x][i-1]][i-1];
}
}
}
void INIT(){
sort(E+1,E+m+1,cmp);
rep(i,1,n)pa[i]=i;
tot=n;
//---
rep(i,1,m){
int fu=GETFA(E[i].u),fv=GETFA(E[i].v);
if(fu==fv)continue;
tot++;
val[tot]=E[i].w;
fa[fu][0]=fa[fv][0]=tot;
son[tot][0]=fu;son[tot][1]=fv;
pa[fu]=pa[fv]=pa[tot]=tot;
}
//---
CHKFA();
rep(i,0,tot)son[i][0]=son[i][1]=0;
tot=0;
rt[0]=1;sg.BUILD(1,1,len);
rep(i,1,n)rt[i]=++tot,sg.INS(rt[i],rt[i-1],1,len,a[pt[i]]);
}
int GET(int x,int mx){
tep(i,20,0){
if((1<<i)>=dep[x])continue;
if(val[fa[x][i]]<=mx)x=fa[x][i];
}
return x;
}
void SOLVE(){
int u,x,K;
scanf("%d%d%d",&u,&x,&K);
int now=GET(u,x);
int L=lef[now],R=rit[now];
printf("%d
",sg.QUE(rt[R],rt[L-1],1,len,sum[rt[R]]-sum[rt[L-1]]-K+1));
}
int main(){
READ();
INIT();
while(T--)SOLVE();
return 0;
}