hogloidのブログ

へなちょこ

The L-th Number

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270

解説にあったみたいに永続を使いました。永続書くのは初めてです
二分探索木はこわいし建て方よくわかったなかったので、せぐつりー風にしました。
ノードごとにlogN個のノードを持って、左・右へのリンクは、
このノードで更新したか、それとも最後に更新されたもっとも近い親のノードはどこかを表します
木をたぐりながら二分探索できるってすごいなぁと思いました。
ソース載せようと思ったのですが、ごちゃごちゃ過ぎて訳分からない疑惑
ですがまあとりあえず載せます。解説書くと日がくれるので、見たい人はみてやってください

#include<cstring>
#include<algorithm>
#include<cstdio>
#define REP(num,num2) for(int num=0;num<(int)(num2);++num)
#define SZ(t) ((int)t.size())
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
using namespace std;
typedef pair<int,int> pi;
int val[400005];
struct segtree{
	int n;
	void init(int n_){
		n=1;
		while(n<n_) n<<=1;
		REP(i,n*2) val[i]=0;
	}
	void add(int k,int a){
		k+=n-1;
		val[k]+=a;
		while(k>0){
			k=(k-1)/2;
			val[k]+=a;
		}
	}
	int query(int node){
		return val[node];
	}
};
segtree sum;
pair<int,pi> seg[100005][20];//inclusible
int whorenew[400005];
int logn,n2;
int n,q;
int head[100005],nxt[200005],es[200005];
int num[100005],zip[100005];
int par[100005];
int par2[20][100005],depth[100005];
int prev[100005][20];
int zn;
void dfs(int v,int p,int dep){
	par2[0][v]=par[v]=p;
	depth[v]=dep;
	int l=0,r=n2;
	sum.add(num[v],1);
	int node=0;
	REP(i,logn){
		seg[v][i].fr=sum.query(node);
		int md=(l+r)>>1;
		prev[dep][i]=whorenew[node];
		whorenew[node]=v;
		if(num[v]<md){
			seg[v][i].sc=mp(v,whorenew[node*2+2]);
			node=node*2+1;
			r=md;
		}else{
			seg[v][i].sc=mp(whorenew[node*2+1],v);
			node=node*2+2;
			l=md;
		}
	}
	seg[v][logn].fr=sum.query(node);
	prev[dep][logn]=whorenew[node];
	whorenew[node]=v;


	for(int i=head[v];i!=-1;i=nxt[i]){
		int to=es[i];
		if(to==p) continue;
		dfs(to,v,dep+1);
	}
	sum.add(num[v],-1);

	l=0;r=n2;
	node=0;
	REP(i,logn){
		int md=(l+r)>>1;
		whorenew[node]=prev[dep][i];
		if(num[v]<md){
			node=node*2+1;
			r=md;
		}else{
			node=node*2+2;
			l=md;
		}
	}
	whorenew[node]=prev[dep][logn];
}
int get2(int rank,int a){
	if(a==-1) return 0;
	int nxt=seg[a][rank].sc.fr;
	if(nxt==-1) return 0;
	int val=seg[nxt][rank+1].fr;
	return val;
}
void renewL(int rank,int& a){
	if(a==-1) return;
	int nxt=seg[a][rank].sc.fr;
	a=nxt;
}
void renewR(int rank,int& a){
	if(a==-1) return;
	int nxt=seg[a][rank].sc.sc;
	a=nxt;
}
int get(int a,int b,int c,int d,int L){
	int l=0,r=n2;
	REP(i,logn){
		int all=get2(i,a)+get2(i,b)-get2(i,c)-get2(i,d),md=(l+r)>>1;
		if(all>=L){
			renewL(i,a);
			renewL(i,b);
			renewL(i,c);
			renewL(i,d);
			r=md;
		}else{
			L-=all;
			renewR(i,a);
			renewR(i,b);
			renewR(i,c);
			renewR(i,d);
			l=md;
		}
	}
	return l;
}

int lca(int a,int b){
	if(depth[a]>depth[b]) swap(a,b);
	int dif=depth[b]-depth[a];
	REP(i,20) if(dif>>i&1) b=par2[i][b];
	if(a==b) return a;
	for(int i=19;i>=0;--i) if(par2[i][a]!=par2[i][b]){
		a=par2[i][a];
		b=par2[i][b];
	}
	return par2[0][a];
}
int main(){
	scanf("%d%d",&n,&q);
	memset(head,-1,sizeof(head));
	REP(i,n){
		int a;scanf("%d",&a);
		num[i]=zip[i]=a;
	}
	sort(zip,zip+n);
	zn=unique(zip,zip+n)-zip;
	REP(i,n){
		num[i]=lower_bound(zip,zip+zn,num[i])-zip;
	}
	logn=0;
	while((1<<logn)<zn) ++logn;
	n2=(1<<logn);
	sum.init(zn);
	int cnt=0;
	REP(i,n-1){
		int a,b;scanf("%d%d",&a,&b);--a;--b;
		nxt[cnt]=head[a];es[cnt]=b;head[a]=cnt++;
		nxt[cnt]=head[b];es[cnt]=a;head[b]=cnt++;
	}
	memset(whorenew,-1,sizeof(whorenew));
	dfs(0,-1,0);
	REP(i,19) REP(j,n){
		if(par2[i][j]==-1) par2[i+1][j]=-1;
		else par2[i+1][j]=par2[i][par2[i][j]];
	}

	REP(i,q){
		int a,b,L;scanf("%d%d%d",&a,&b,&L);--a;--b;
		printf("%d\n",zip[get(a,b,lca(a,b),par[lca(a,b)],L)]);
	}
	return 0;
}