RT

顺便问一下为啥一直在waiting

Code：

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
int n,m,x,y,las,lgs[100005],C[100005],blo2,D[200005],h[100005],vis[100005],ans[100005],Sl,Sr,blck[405],blo,dep[100005],fa[100005][25],Fi[100005],Se[100005],path[200005],r,a[100005],c[100005],qn;
vector<int> G[100005];
struct node{
	int u,v,l,r,k,lca,id;
}qry[100005];
int cmp(node x,node y){
	return (D[x.l]==D[y.l])?(x.r==y.r?0:((D[x.l])&1)^(x.r<y.r)):(x.l<y.l);;
}
void dfs(int x,int fat){
	fa[x][0]=fat;
	dep[x]=dep[fat]+1;
	path[++r]=x;
	for(int i=1;i<=lgs[dep[x]];i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=0;i<G[x].size();i++){
		if(G[x][i]==fat){
			continue;
		}
		dfs(G[x][i],x);
	}
	path[++r]=x;
}
int LCA(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);
	}
	while(dep[y]>dep[x]){
		y=fa[y][lgs[dep[y]-dep[x]]];
	}
	if(x==y){
		return x;
	}
	for(int k=lgs[dep[x]];k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
void modify(int x){
	if(!x){
		return ;
	}
	int pas=path[x],val;
	val=a[pas];
	if(vis[pas]){
		h[val]--;
		blck[C[val]]--;
	}
	else{
		h[val]++;
		blck[C[val]]++;
	}
	vis[pas]^=1;
}
void modify2(int pas){
	int val;
	val=a[pas];
	if(vis[pas]){
		h[val]--;
		blck[C[val]]--;
	}
	else{
		h[val]++;
		blck[C[val]]++;
	}
	vis[pas]^=1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=a[i];
	}
	for(int i=2;i<=n;i++){
		lgs[i]=lgs[i>>1]+1;
	}
	sort(c+1,c+n+1);
	qn=unique(c+1,c+n+1)-c-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(c+1,c+qn+1,a[i])-c;
	}
	for(int i=1;i<=n-1;i++){
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x); 
	}
	dfs(1,0);
	for(int i=1;i<=r;i++){
		Se[path[i]]=i;
	}
	for(int i=r;i>=1;i--){
		Fi[path[i]]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>qry[i].u>>qry[i].v>>qry[i].k;
		qry[i].id=i;
		if(Fi[qry[i].u]>Fi[qry[i].v]){
			swap(qry[i].u,qry[i].v);
		}
		qry[i].lca=LCA(qry[i].u,qry[i].v);
		if(qry[i].lca==qry[i].u){
			qry[i].lca=0;
			qry[i].l=Fi[qry[i].u];
			qry[i].r=Fi[qry[i].v];
		}
		else{
			qry[i].l=Se[qry[i].u];
			qry[i].r=Fi[qry[i].v];
		}
	}
	blo=int((double)r/(double)sqrt(m));
	blo2=int(sqrt(qn));
	for(int i=1;i<=r;i++){
		D[i]=i/blo;
	}
	sort(qry+1,qry+m+1,cmp);
	for(int i=1;i<=n;i++){
		C[i]=(i-1)/blo2+1;
	}
	for(int i=1;i<=m;i++){
		if(i==70000){
			cout<<"CODER"<<endl;
		}
		while(Sl<qry[i].l){
			modify(Sl++);
		}
		while(Sl>qry[i].l){
			modify(--Sl);
		}
		while(Sr<qry[i].r){
			modify(++Sr);
		}
		while(Sr>qry[i].r){
			modify(Sr--);
		}
		if(qry[i].lca){
			modify2(qry[i].lca);
			for(int ii=1;ii<=C[qn];ii++){
				if(blck[ii]<qry[i].k){
					qry[i].k-=blck[ii];
				}
				else{
					for(int jj=(ii-1)*blo2+1;jj<=ii*blo2;jj++){
						if(h[jj]<qry[i].k){
							qry[i].k-=h[jj];
						}
						else{
							ans[qry[i].id]=c[jj];
							break;
						}
					}
					break;
				}
			}
			modify2(qry[i].lca);
		}
		else{
			for(int ii=1;ii<=C[qn];ii++){
				if(blck[ii]<qry[i].k){
					qry[i].k-=blck[ii];
				}
				else{
					for(int jj=(ii-1)*blo2+1;jj<=min(ii*blo2,qn);jj++){
						if(h[jj]<qry[i].k){
							qry[i].k-=h[jj];
						}
						else{
							ans[qry[i].id]=c[jj];
							break;
						}
					}
					break;
				}
			}
		}
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}