记录编号	412363	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]树白黑	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.181 s
提交时间	2017-06-08 21:36:46	内存使用	363.46 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=4e5+10,M=3e7+10;
struct Node{int l,r,v;}node[M];
int root[N],id;
int add(int x,int l,int r,int p){
	int now=++id;
	node[now]=node[x];
	node[now].v++;
	if (l==r) return now;
	int mid=(l+r)>>1;
	if (p>mid) node[now].r=add(node[x].r,mid+1,r,p);
		else node[now].l=add(node[x].l,l,mid,p);
	return now;
}
int query(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return node[x].v;
	int mid=(l+r)>>1,ans=0;
	if (L<=mid) ans+=query(node[x].l,l,mid,L,R);
	if (R>mid) ans+=query(node[x].r,mid+1,r,L,R);
	return ans;
}
int n,m,q,w[N],fa[N],s[N],big[N],head[N],next[N];
void add(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
void dfs(int x){
	s[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i]]){
		int v=w[i];
		fa[v]=x;
		dfs(v);
		s[x]+=s[v];
		if (s[v]>s[big[x]]) big[x]=v;
	}
}
int dfn[N],link[N],h[N];
vector<int> Q[N];
void po(int x){
	static int cnt=0;
	dfn[x]=++cnt;
	link[x]=(dfn[x]==dfn[fa[x]]+1?link[fa[x]]:x);
	Q[link[x]].push_back(x);
	h[x]=Q[link[x]].size()-1;
	if (!big[x]) return;
	po(big[x]);
	for (int i=head[x];i;i=next[i])
	if (w[i]!=big[x]&&w[i]!=fa[x]) po(w[i]);
}
int l,r,u;
bool check(int x){
	return query(root[r],1,n,dfn[x],dfn[x]+s[x]-1)
		-query(root[l-1],1,n,dfn[x],dfn[x]+s[x]-1)>0;
}
int solve(int l,int r,vector<int> &a){
	if (l==r) return a[l];
	int mid=(l+r)>>1;
	return check(a[mid+1])?solve(mid+1,r,a):solve(l,mid,a);
}
int main()
{
	freopen("B_Tree.in","r",stdin);
	freopen("B_Tree.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	fa[1]=1;dfs(1);po(1);
	for (int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);
		root[i]=add(root[i-1],1,n,dfn[x]);
	}
	while (q--){
		scanf("%d%d%d",&l,&r,&u);
		for (;!check(link[u]);u=fa[link[u]]);
		printf("%d\n",solve(0,h[u],Q[link[u]]));
	}
	return 0;
}