记录编号	445078	评测结果	AAAAAATAAA
题目名称	mk和tree	最终得分	90
用户昵称	Ostmbh	是否通过	未通过
代码语言	C++	运行时间	2.050 s
提交时间	2017-09-04 22:02:50	内存使用	18.62 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 top[maxn],dep[maxn],fa[maxn],size[maxn],son[maxn];
int tot=0;
inline void dfs1(int x,int f,int d){
	dep[x]=d;
	fa[x]=f;
	size[x]=1;
	for(int i=0;i<A[x].size();i++){
		int 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]);
	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);
		tot=0;
		while(x!=fa[lc]){
			B[++tot]=v[x];
			x=fa[x];
		}
		while(y!=lc){
			B[++tot]=v[y];
			y=fa[y];
		}
		sort(B+1,B+tot+1);
		printf("%d\n",B[z]);
	}
	//cout<<m<<endl;
return 0;
}