记录编号	390655	评测结果	AAAAAAAAAA
题目名称	2280.[HZOI 2015]树白黑	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.394 s
提交时间	2017-04-03 17:18:13	内存使用	93.39 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=200010,maxm=maxn<<5;
void bfs();
void add(int,int,int&);
int merge(int,int);
void query(int,int,int);
int sm[maxm]={0},lc[maxm]={0},rc[maxm]={0},root[maxn]={0},cnt=0;
vector<int>G[maxn];
int f[maxn][20]={{0}},d[maxn],q[maxn];
int n,m,k,lgn=0,x,y,s,t,tmp;
int main(){
	freopen("B_Tree.in","r",stdin);
	freopen("B_Tree.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(t=1;t<=m;t++){
		scanf("%d",&x);
		add(1,m,root[x]);
	}
	bfs();
	for(int j=1;j<=lgn;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];
	
	while(k--){
		scanf("%d%d%d",&s,&t,&x);
		tmp=0;
		query(1,m,root[x]);
		if(tmp)printf("%d\n",x);
		else{
			for(int i=lgn;i>=0;i--)if(f[x][i]){
				tmp=0;
				query(1,m,root[f[x][i]]);
				if(!tmp)x=f[x][i];
			}
			printf("%d\n",f[x][0]);
		}
	}
	return 0;
}
void bfs(){
	int x,head=0,tail=0;
	q[tail++]=1;
	while(head!=tail){
		x=q[head++];//printf("%d\n",x);
		d[x]=d[f[x][0]]+1;
		while((1<<lgn)<d[x])lgn++;
		for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=f[x][0]){
			f[G[x][i]][0]=x;
			q[tail++]=G[x][i];
		}
	}
	for(int i=tail-1;i;i--)root[f[q[i]][0]]=merge(root[f[q[i]][0]],root[q[i]]);
}
void add(int l,int r,int &rt){
	if(!rt)rt=++cnt;
	sm[rt]++;
	if(l==r)return;
	int mid=(l+r)>>1;
	if(t<=mid)add(l,mid,lc[rt]);
	else add(mid+1,r,rc[rt]);
}
int merge(int x,int y){
	if(!x)return y;
	if(!y)return x;
	int rt=++cnt;
	sm[rt]=sm[x]+sm[y];
	lc[rt]=merge(lc[x],lc[y]);
	rc[rt]=merge(rc[x],rc[y]);
	return rt;
}
void query(int l,int r,int rt){
	if(!rt)return;
	if(s<=l&&t>=r){
		tmp+=sm[rt];
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)query(l,mid,lc[rt]);
	if(t>mid)query(mid+1,r,rc[rt]);
}