题意:给定一个无向图,询问从一个点出发只经过不超过指定边权的边能到达的点的第$k$大点权
这道题可以离线也可以在线做
bzoj上有强制在线的加强版
离线做法就是用线段树维护联通块,启发式合并即可。
这里采用在线做法:$Kruskal$重构树
这个算法是NOI2018 D1T1的解法
如果有不会的同学可以自行学习
这道题步骤如下:
先构造$Kruskal$重构树
用倍增找到x在最小生成树上的瓶颈(边权不超过y)
然后查询这个点的子树中的第k小值
然后?就没了orzzzzzz
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=2e5+5,M=5e5+5;
struct E
{
int from,to,dis;
inline friend bool operator < (E a,E b) {return a.dis<b.dis;}
}e[M];
struct node
{
int to,nxt;
}edge[N<<2];
int n,m,T,num,head[N],fa[N],noww,val[N],cnt,L[N],R[N],tim,tot;
int f[N][20],sum[N*30],ls[N*30],rs[N*30],a[N],w[N],t[N],rt[N];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void add_edge(int from,int to)
{
edge[++num]=(node){to,head[from]};
head[from]=num;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void Kruskal()
{
for (reg int i=1;i<=n;i++) fa[i]=i;
for (reg int i=1,tt=0;i<=m;i++)
{
int x=find(e[i].from),y=find(e[i].to);
if (x==y) continue;
val[++cnt]=e[i].dis;
add_edge(cnt,x); add_edge(cnt,y);
fa[x]=fa[y]=fa[cnt]=cnt;
if (++tt==n-1) break;
}
}
void dfs(int k,int fh)
{
L[k]=++tim; a[tim]=k; f[k][0]=fh;
for (reg int i=1;i<=19;i++) f[k][i]=f[f[k][i-1]][i-1];
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (v!=fh) dfs(v,k);
}
R[k]=tim;
}
void insert(int &now,int pre,int l,int r,int x)
{
now=++tot; sum[now]=sum[pre]+1;
ls[now]=ls[pre]; rs[now]=rs[pre];
if (l>=r) return; int mid=(l+r)>>1;
if (x<=mid) insert(ls[now],ls[now],l,mid,x);
else insert(rs[now],rs[now],mid+1,r,x);
}
int query(int now,int pre,int l,int r,int x)
{
if (l>=r) return l;
int mid=(l+r)>>1,tmp=sum[ls[now]]-sum[ls[pre]];
if (x<=tmp) return query(ls[now],ls[pre],l,mid,x);
return query(rs[now],rs[pre],mid+1,r,x-tmp);
}
int main()
{
cnt=n=read(),m=read(),T=read();
for (reg int i=1;i<=n;i++) w[i]=t[i]=read();
for (reg int i=1;i<=m;i++)
e[i].from=read(),e[i].to=read(),e[i].dis=read();
sort(t+1,t+n+1); sort(e+1,e+m+1);
noww=unique(t+1,t+n+1)-t-1;
for (reg int i=1;i<=n;i++) w[i]=lower_bound(t+1,t+noww+1,w[i])-t;
Kruskal(); dfs(cnt,cnt);
for (reg int i=1;i<=cnt;i++)
if (a[i]<=n) insert(rt[i],rt[i-1],1,noww,w[a[i]]); else rt[i]=rt[i-1];
while (T--)
{
int x=read(),y=read(),k=read(),ans;
for (reg int i=19;~i;i--) if (val[f[x][i]]<=y) x=f[x][i];
int res=sum[rt[R[x]]]-sum[rt[L[x]-1]];
if (res<k) ans=-1;
else ans=t[query(rt[R[x]],rt[L[x]-1],1,noww,res-k+1)];
printf("%d\n",ans);
}
return 0;
}
```