RE求助
查看原帖
RE求助
989792
lrx___楼主2024/10/22 20:01
#include <cstdio>
#include <algorithm>

const int A(1e5+5);
int n,m,a[A],li[A],fa[A][18],dep[A],unq;
class node{
	public:
		int sz;
		node *ls,*rs;
}t[A<<5],*root[A],*tot;
class graph{
	public:
		int h[A],e[A][2],p;
		void init(int n){
			std::fill(h+1,h+n+1,-1);
			p=0;
		}
		void add(int u,int v){
			e[p][0]=h[u];e[p][1]=v;
			h[u]=p++;
			e[p][0]=h[v];e[p][1]=u;
			h[v]=p++;
		}
}g;

void update(node*& u,int k,node*& f,int l=1,int r=unq){
	u=++tot;
	u->ls=f->ls;u->rs=f->rs;u->sz=f->sz+1;
	if(l==r){
		return;
	}
	int mid((l+r)>>1);
	if(k<=mid){
		update(u->ls,k,f->ls,l,mid);
	}else{
		update(u->rs,k,f->rs,mid+1,r);
	}
}
int query(node*& u,node*& v,node*& lca,node*& lca_fa,int k,int l=1,int r=unq){
	if(l==r){
		return l;
	}
	int mid((l+r)>>1),left(u->ls->sz+v->ls->sz-lca->ls->sz-lca_fa->ls->sz);
	if(k<=left){
		return query(u->ls,v->ls,lca->ls,lca_fa->ls,k,l,mid);
	}else{
		return query(u->rs,v->rs,lca->rs,lca_fa->rs,k-left,mid+1,r);
	}
}
void dfs(int u,int father=0){
	update(root[u],a[u],root[*fa[u]=father]);
	dep[u]=dep[father]+1;
	for(int e(g.h[u]),v;~e;e=g.e[e][0]){
		v=g.e[e][1];
		if(v!=father){
			dfs(v,u);
		}
	}
}
int get_lca(int u,int v){
	if(dep[u]<dep[v]){
		std::swap(u,v);
	}
	for(int i(17);~i;--i){
		if(dep[fa[u][i]]>=dep[v]){
			u=fa[u][i];
		}
	}
	if(u==v){
		return u;
	}
	for(int i(17);~i;--i){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];v=fa[v][i];
		}
	}
	return *fa[u];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i(1);i<=n;++i){
		scanf("%d",a+i);
		li[i]=a[i];
	}
	std::sort(li+1,li+n+1);
	unq=std::unique(li+1,li+n+1)-li-1;
	for(int i(1);i<=n;++i){
		a[i]=std::lower_bound(li+1,li+unq+1,a[i])-li;
	}
	g.init(n);
	root[0]=tot=t->ls=t->rs=t;
	for(int i(1),u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		g.add(u,v);
	}
	dfs(1,0);
	for(int i(1),j;i<18;++i){
		for(j=1;j<=n;++j){
			fa[j][i]=fa[fa[j][i-1]][i-1];
		}
	}
	for(int i(0),u,v,k,lca;i<m;++i){
		scanf("%d%d%d",&u,&v,&k);
		lca=get_lca(u,v);
		printf("%d\n",li[query(root[u],root[v],root[lca],root[*fa[lca]],k)]);
	}
	return 0;
}
2024/10/22 20:01
加载中...