题意
给定一颗有点权以及边权树以及若干询问，每次求从给定节点出发经过长度均不超过k的边能达到的点中，第k高的点的点权。
思路
看到对边长度的限制，没有思路。
提高知识水平之后发现有所谓kruskal重构树这一操作。（提高关键词敏感度）
kruskal重构树的原理及实现细节放到另一篇文章里面写，这里默认所有人都会了。
那么对于询问中的边权限制，其实我们就是在主席树上查询点权小于等于k的节点的子树中的k大值。
代码
#include <bits/stdc++.h>
using namespace std;
namespace StandardIO {
template<typename T>inline void read (T &x) {
x=0;T f=1;char c=getchar();
for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T>inline void write (T x) {
if (x<0) putchar('-'),x*=-1;
if (x>=10) write(x/10);
putchar(x%10+'0');
}
}
using namespace StandardIO;
namespace Project {
const int N=500001;
int n,m,q,len;
int h[N],b[N];
struct node {
int from,to,val;
} edge[N];
int cnt,tot;
int head[N];
struct gnode {
int to,next;
} G[N];
int tmp;
int fa[N],val[N],range[N][2],f[N][21];
int nodes;
int root[N];
struct tnode {
int ls,rs,val;
} tree[N*21];
inline void add (int a,int b) {
G[++cnt].to=b,G[cnt].next=head[a],head[a]=cnt;
}
inline bool cmp (node x,node y) {
return x.val<y.val;
}
inline int find (int x) {
return (x==fa[x])?x:fa[x]=find(fa[x]);
}
void build (int l,int r,int &pos) {
pos=++nodes;
if (l==r) return;
int mid=(l+r)>>1;
build(l,mid,tree[pos].ls),build(mid+1,r,tree[pos].rs);
}
void update (int l,int r,int v,int las,int &pos) {
pos=++nodes;
tree[pos]=tree[las],++tree[pos].val;
if (l==r) return;
int mid=(l+r)>>1;
if (v<=mid) update(l,mid,v,tree[las].ls,tree[pos].ls);
else update(mid+1,r,v,tree[las].rs,tree[pos].rs);
}
int query (int l,int r,int k,int las,int now) {
if (l==r) return l;
int mid=(l+r)>>1,t=tree[tree[now].rs].val-tree[tree[las].rs].val;
if (k<=t) return query(mid+1,r,k,tree[las].rs,tree[now].rs);
return query(l,mid,k-t,tree[las].ls,tree[now].ls);
}
void dfs (int now) {
for (register int i=1; i<=20; ++i) {
f[now][i]=f[f[now][i-1]][i-1];
}
range[now][0]=tmp;
if (!head[now]) return range[now][0]=++tmp,update(1,len,lower_bound(b+1,b+len+1,h[now])-b,root[tmp-1],root[tmp]),void();
for (register int i=head[now]; i; i=G[i].next) {
int to=G[i].to;
dfs(to);
}
range[now][1]=tmp;
}
inline void MAIN () {
read(n),read(m),read(q);
for (register int i=1; i<=n; ++i) {
read(h[i]),b[i]=h[i],fa[i]=i;
}
sort(b+1,b+n+1),len=unique(b+1,b+n+1)-b-1;
for (register int i=1; i<=m; ++i) {
read(edge[i].from),read(edge[i].to),read(edge[i].val);
}
sort(edge+1,edge+m+1,cmp),tot=n;
for (register int i=1; i<=m; ++i) {
int x=find(edge[i].from),y=find(edge[i].to);
if (x==y) continue;
val[++tot]=edge[i].val,fa[tot]=fa[x]=fa[y]=tot,f[x][0]=f[y][0]=tot;
add(tot,x),add(tot,y);
}
build(1,len,root[0]);
dfs(tot);
while (q--) {
int x,y,z;
read(x),read(y),read(z);
for (register int i=20; i>=0; --i) {
if (f[x][i]&&val[f[x][i]]<=y) x=f[x][i];
}
if (tree[root[range[x][1]]].val-tree[root[range[x][0]]].val<z) {
write(-1);
} else {
write(b[query(1,len,z,root[range[x][0]],root[range[x][1]])]);
}
putchar('
');
}
}
}
int main () {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Project::MAIN();
}
后记
恩？？竟然有后记？？
其实就是吐槽一下，这道题空间我开的很玄学，至今没有搞懂原理。（每次主席树的题都得调空间。。。）
顺便口胡一下离线做法：大概就是枚举权值，然后每次把点权小于权值的点两边合并一下，然后查询k大值。