记录编号	458206	评测结果	AAAAAAAAAA
题目名称	mk和tree	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.867 s
提交时间	2017-10-10 16:37:29	内存使用	39.23 MiB

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}
const int maxn=100010;
int n,m;
vector<int>t[maxn];
struct dd{
	int x,id;
}data[maxn];
inline bool cmp(dd a,dd b){return a.x<b.x;}
int rk[maxn],sz[maxn],dep[maxn],fa[maxn],son[maxn],top[maxn],tot;
inline void dfs1(int u,int f,int d){
	sz[u]=1;fa[u]=f;dep[u]=d;
	for(int i=0;i<(int)t[u].size();i++){
		int v=t[u][i];
		if(v==f)continue;
		dfs1(v,u,d+1);
		sz[u]+=sz[v];
		if(!son[u]||sz[son[u]]<sz[v])son[u]=v;
	}
}
inline void dfs2(int u,int tou){
	top[u]=tou;
	if(!son[u])return ;
	dfs2(son[u],tou);
	for(int i=0;i<(int)t[u].size();i++){
		int v=t[u][i];
		if(v!=son[u]&&v!=fa[u])dfs2(v,v);
	}
}
inline int lca(int x,int y){
	int u=top[x],v=top[y];
	while(u!=v){
		if(dep[u]<dep[v])swap(u,v),swap(x,y);
		x=fa[u],u=top[x];
	}
	return dep[x]<dep[y]?x:y;
}
int sum[maxn*30],ls[maxn*30],rs[maxn*30],size,gen[maxn];
inline void change(int shang,int & xin,int l,int r,int nl,int nr){
	xin=++size;
	if(l>=nl&&r<=nr){
		sum[xin]=sum[shang]+1;
		return ;
	}
	int m=(l+r)>>1;
	ls[xin]=ls[shang];
	rs[xin]=rs[shang];
	if(m>=nl)change(ls[shang],ls[xin],l,m,nl,nr);
	if(m<nr)change(rs[shang],rs[xin],m+1,r,nl,nr);
	sum[xin]=sum[ls[xin]]+sum[rs[xin]];
}
inline int kth(int s1,int s2,int x1,int x2,int l,int r,int k){
	if(l==r)return l;
	int lsum=sum[ls[x1]]+sum[ls[x2]]-sum[ls[s1]]-sum[ls[s2]];
	int m=(l+r)>>1;
	if(k<=lsum)return kth(ls[s1],ls[s2],ls[x1],ls[x2],l,m,k);
	else return kth(rs[s1],rs[s2],rs[x1],rs[x2],m+1,r,k-lsum);
}
inline void dfs(int u,int f){//建树，建立以1为根到u节点的权值线段树; 
	change(gen[f],gen[u],1,n,rk[u],rk[u]);
	for(int i=0;i<(int)t[u].size();i++){
		int v=t[u][i];
		if(v==f)continue;
		dfs(v,u);
	}
}
inline int find(int s1,int s2,int x1,int x2,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return sum[x1]+sum[x2]-sum[s1]-sum[s2];
	int m=(l+r)>>1;
	int ans=0;
	if(m>=nl)ans+=find(ls[s1],ls[s2],ls[x1],ls[x2],l,m,nl,nr);
	if(m<nr)ans+=find(rs[s1],rs[s2],rs[x1],rs[x2],m+1,r,nl,nr);
	return ans;
}
int main(){
	freopen("mktree.in","r",stdin);
	freopen("mktree.out","w",stdout);
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		t[u].push_back(v);
		t[v].push_back(u);  
	}
	for(int i=1;i<=n;i++){
		data[i].x=read();
		data[i].id=i;
	}
	sort(data+1,data+n+1,cmp);
	for(int i=1;i<=n;i++)rk[data[i].id]=i;
	dfs1(1,0,1);dfs2(1,1);dfs(1,0);
	m=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),k=read();
		int lc=lca(x,y);
		printf("%d\n",data[kth(gen[lc],gen[fa[lc]],gen[x],gen[y],1,n,k)].x);
	}
	return 0;
}