@[guoxiangyu66](/user/681036) 什么算法啊，克鲁斯卡尔重构树？明天来帮你调
by 北文 @ 2023-04-27 21:38:27
@[北文](/user/53769) 是 kruskal 重构树
by OldDriverTree @ 2023-04-27 21:39:36
@[guoxiangyu66](/user/681036) 我失误了，我写了线段树合并，你这个主席树，我猜测是你建树的时候顺序有问题，你怎么能按dfs序的顺序建树呢？我认为可能需要通过dfs建树
by 北文 @ 2023-04-28 08:24:20
@[北文](/user/53769) 哦，thx，我傻逼了
by OldDriverTree @ 2023-04-28 11:23:33
@[北文](/user/53769) 谢谢，但是 #2 怎么又 TLE 了呀？
```c++
#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=2e5,M=5e5;
int L[N],R[N],root[N];
int f[N][18],size[N];
vector<int> g[N],num;
int n,q,cnt,a[N],pos[N];
void add(int x,int y) {
g[x].push_back(y);
}
namespace SGT
{
int tot;
struct node {
int l,r,cnt;
}T[N*10];
void build(int &rt,int l,int r) {
rt=(++tot); if (l==r) return;
build(T[rt].l,l,mid),build(T[rt].r,mid+1,r);
}
void update(int &q,int p,int l,int r,int pos) {
q=(++tot),T[q]=T[p],T[q].cnt++; if (l==r) return;
if (pos<=mid) update(T[q].l,T[p].l,l,mid,pos);
else update(T[q].r,T[p].r,mid+1,r,pos);
}
int query(int p,int q,int l,int r,int k) {
if (l==r) return l; int res=T[T[p].r].cnt-T[T[q].r].cnt;
if (k<=res) return query(T[p].r,T[q].r,mid+1,r,k);
else return query(T[p].l,T[q].l,l,mid,k-res);
}
}using namespace SGT;
namespace GT
{
int tot; void dfs(int u,int fa) {
pos[++tot]=u,L[u]=tot; if (g[u].empty() ) size[u]=1;
f[u][0]=fa; for (int i=1;i<18;i++) f[u][i]=f[f[u][i-1] ][i-1];
for (int v:g[u]) dfs(v,u),size[u]+=size[v]; R[u]=tot;
}
}using namespace GT;
namespace Kruskal
{
int m,fa[N];
int find(int x) {
return fa[x]^x?find(fa[x]):x;
}
struct edge
{
int x,y,z;
bool operator <(edge o)const {
return z<o.z;
}
}e[M];
void kruskal()
{
for (int i=1;i<=n;i++) fa[i]=i;
sort(e,e+m); for (int i=0;i<m;i++)
{
int x=find(e[i].x),y=find(e[i].y);
if (x==y) continue; a[++cnt]=e[i].z;
add(cnt,x),add(cnt,y); fa[x]=fa[y]=fa[cnt]=cnt;
}for (int i=1;i<=cnt;i++) if (!pos[i]) dfs(find(i),0);
}
}using namespace Kruskal;
int main()
{
scanf("%d%d%d",&n,&m,&q); for (int i=1;i<=n;i++) scanf("%d",&a[i]); cnt=n;
for (int i=0;i<m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); kruskal();
for (int i=1;i<=n;i++) num.push_back(a[i]); sort(num.begin(),num.end() );
num.erase(unique(num.begin(),num.end() ),num.end() ); a[0]=2e9;
build(root[0],0,num.size()-1); for (int i=1,p;i<=cnt;i++) {
if (pos[i]<=n) p=lower_bound(num.begin(),num.end(),a[pos[i] ])-num.begin();
if (pos[i]<=n) update(root[i],root[i-1],0,num.size()-1,p); else root[i]=root[i-1];
}while (q--) {
int x,v,k; scanf("%d%d%d",&x,&v,&k);
for (int i=17;i>=0;i--) if (a[f[x][i] ]<=v) x=f[x][i];
int ans=num[query(root[R[x] ],root[L[x]-1],0,num.size()-1,k)];
printf("%d\n",size[x]<k?-1:ans);
}return 0;
}
```
by OldDriverTree @ 2023-04-28 11:28:10
@[guoxiangyu66](/user/681036) 我怎么知道你等我看一眼
by 北文 @ 2023-04-28 11:40:58
我饿了，要吃饭 你自己调吧
by 北文 @ 2023-04-28 11:42:44
此贴结，并查集没加路径压缩，已 A
by OldDriverTree @ 2023-04-28 22:02:25