题目:
在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。
题解:
这道题貌似是Kruskal重构树的板子题.
很长时间以前做了加强版,现在才发现还有未加强版.
赶紧把代码粘了过来水了过去.
(还记得写这份代码的时候被卡内存,用了po姐的主席树模板才过去的)
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 200200;
const int inf = 0x3f3f3f3f;
struct Edge{
int to,next;
}G[maxn];
int head[maxn],cnt;
void add(int u,int v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
struct edge{
int u,v,d;
bool friend operator < (const edge &a,const edge &b){
return a.d < b.d;
}
}zs[500500];
int n,w[maxn],ufa[maxn],m,q;
int fa[maxn][20],dis[maxn][20];
int find(int u){
return ufa[u] == u ? u : ufa[u] = find(ufa[u]);
}
void Kruskal(){
sort(zs+1,zs+m+1);
int nc = 0;
for(int i=1;i<=m;++i){
int x = find(zs[i].u);
int y = find(zs[i].v);
if(x != y){
ufa[x] = ufa[y] = ++n;
ufa[n] = n;
fa[x][0] = n;fa[y][0] = n;
dis[x][0] = dis[y][0] = zs[i].d;
add(n,x);add(n,y);
if(++nc == n-1) break;
}
}
}
int dfn[maxn],ind[maxn],oud[maxn];
int dfs_clock;
#define v G[i].to
void dfs(int u){
ind[u] = ++dfs_clock;
dfn[ind[u]] = w[u];
for(int i = head[u];i;i=G[i].next){
dfs(v);
}
oud[u] = dfs_clock;
}
#undef v
struct Node{
Node *ls,*rs;
int num;
void* operator new (size_t size,Node *_,Node *__,int ___);
}*tree[maxn],*mempool,*C,*null;
void* Node :: operator new (size_t size,Node *_,Node *__,int ___){
if(C==mempool){
C=new Node[1<<15];
mempool=C+(1<<15);
}
C->ls=_;
C->rs=__;
C->num=___;
return C++;
}
Node* build(Node *p,int x,int y,int val){
int mid=x+y>>1;
if(x==y) return new (null,null,p->num+1) Node;
if(val<=mid) return new (build(p->ls,x,mid,val),p->rs,p->num+1) Node;
else return new (p->ls,build(p->rs,mid+1,y,val),p->num+1) Node;
}
int Kth(Node *p1,Node *p2,int x,int y,int k){
int l = x,r = y;
while(l != r){
int x = p2->rs->num-p1->rs->num;
int mid = l+r >> 1;
if(k <= x){
p1 = p1->rs;p2 = p2->rs;
l = mid+1;
}else{
p1 = p1->ls;p2 = p2->ls;
r = mid;k -= x;
}
}return l;
}
int get_rt(int x,int y){
for(int j=19;~j;--j){
if(fa[x][j] && dis[x][j] <= y){
x = fa[x][j];
}
}
return x;
}
int main(){
read(n);read(m);read(q);
for(int i=1;i<=n;++i){
read(w[i]);ufa[i] = i;
}
for(int i=1;i<=m;++i){
read(zs[i].u);read(zs[i].v);
read(zs[i].d);
}
Kruskal();
for(int j = 1;j<= 19;++j){
for(int i=1;i<=n;++i){
fa[i][j] = fa[fa[i][j-1]][j-1];
dis[i][j] = cat_max(dis[i][j-1],dis[fa[i][j-1]][j-1]);
}
}
dfs(n);
null=new (0x0,0x0,0) Node;
null->ls=null->rs=null;
tree[0] = null;
for(int i=1;i<=n;++i){
tree[i] = build(tree[i-1],0,1000000000,dfn[i]);
}
int u,v,k,ans = 0;
while(q--){
read(u);read(v);read(k);
int x = get_rt(u,v);
if(oud[x] - ind[x] + 1 < k){
puts("-1");
ans = 0;
continue;
}
ans = Kth(tree[ind[x]-1],tree[oud[x]],0,1000000000,k);
if(ans == 0){
puts("-1");
continue;
}
printf("%d
",ans);
}
getchar();getchar();
return 0;
}