记录编号	444350	评测结果	AAAAAAAAAA
题目名称	2790.mk和tree	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	1.279 s
提交时间	2017-09-02 17:38:08	内存使用	171.60 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=100000+10;
vector<int>A[maxn];
int v[maxn];
int B[maxn];
int hash[maxn];
int root[maxn*100],ls[maxn*100],rs[maxn*100];
int sum[maxn*100];
int top[maxn],dep[maxn],fa[maxn],size[maxn],son[maxn];
int tot=0;
int sz=0;
inline int bs(int x){
	int l=1,r=tot;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(hash[mid]>=x)
			r=mid;
		else l=mid+1;
	}
	if(hash[l]==x)
		return l;
	else return r;
}
inline void insert(int &rt,int y,int l,int r,int x){
	rt=++sz;
	sum[rt]=sum[y]+1;
	ls[rt]=ls[y];
	rs[rt]=rs[y];
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	if(mid>=x)
		insert(ls[rt],ls[y],l,mid,x);
	else insert(rs[rt],rs[y],mid+1,r,x);
}
inline int query(int u,int v,int lca,int fl,int l,int r,int k){
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	int tmp=sum[ls[u]]+sum[ls[v]]-sum[ls[fl]]-sum[ls[lca]];
	if(tmp>=k)
		return query(ls[u],ls[v],ls[lca],ls[fl],l,mid,k);
	else return query(rs[u],rs[v],rs[lca],rs[fl],mid+1,r,k-tmp);
}
inline void dfs1(int x,int f,int d){
	dep[x]=d;
	fa[x]=f;
	int u=bs(v[x]);
	insert(root[x],root[f],1,tot,u);
	size[x]=1;
	for(int i=0;i<A[x].size();i++){
		u=A[x][i];
		if(u==f)
			continue;
		dfs1(u,x,d+1);
		size[x]+=size[u];
		if((size[u]>size[son[x]]&&son[x])||!son[x])
			son[x]=u;
	}
}
inline void dfs2(int x,int tp){
	top[x]=tp;
	if(!son[x])
		return ;
	dfs2(son[x],tp);
	for(int i=0;i<A[x].size();i++){
		int u=A[x][i];
		if(u==son[x]||u==fa[x])
			continue;
		dfs2(u,u);
	}
}
inline int Lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])
		swap(x,y);
	return x;
}
int main(){
	freopen("mktree.in","r",stdin);
	freopen("mktree.out","w",stdout);
	int n;	
	scanf("%d",&n);
	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d %d",&x,&y);
		A[x].push_back(y);
		A[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i]);
		B[i]=v[i];
	}
	sort(B+1,B+n+1);
	hash[++tot]=B[1];
	for(int i=2;i<=n;i++)
		if(B[i]!=B[i-1])
			hash[++tot]=B[i];
	dfs1(1,0,1);
	dfs2(1,1);
	int m;
	scanf("%d",&m);
	int z;
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&z);
		int lc=Lca(x,y);
		printf("%d\n",hash[query(root[x],root[y],root[lc],root[fa[lc]],1,tot,z)]);
	}
return 0;
}