RT，树剖套的分块，42分

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],u,v,p[100005],sum[100005],top[100005];
int son[100005],dep[100005],size[100005],f[100005];
int begin[100005],end[100005],s[100005],block,cnt;
vector<int>ve[100005];
void dfs1(int now,int fa,int deep) {
	dep[now]=deep;
	f[now]=fa;
	size[now]=1;
	int maxsize=0;
	for(int i=0; i<ve[now].size(); i++) {
		int y=ve[now][i];
		if(y==fa)continue;
		dfs1(y,now,deep+1);
		if(size[y]>maxsize)maxsize=size[y],son[now]=y;
		size[now]+=size[y];
	}
	return;
}
void dfs2(int now,int _top) {
	top[now]=_top;
	p[now]=++cnt;
	sum[cnt]=a[now];
	if(!son[now])return;
	dfs2(son[now],_top);
	for(int i=0; i<ve[now].size(); i++) {
		int y=ve[now][i];
		if(y==f[now]||y==son[now])continue;
		dfs2(y,y);
	}
	return;
}
void build() {
	block=100;
	int total=0;
	for(int i=1; i<=n; i++)s[i]=sum[i];
	for(int i=1; i<=n; i+=block) {
		total++;
		begin[total]=i;
		end[total]=min(n,i+block-1);
		sort(s+i+1,s+min(n,i+block-1)+1);
	}
	return;
}
bool find1(int l,int r,int k) {
	int numl=l/block+(l%block!=0),numr=r/block+(r%block!=0);
	if(numl==numr) {
		for(int i=l; i<=r; i++)if(sum[i]==k)return true;
		return false;
	}
	for(int i=l; i<=end[numl]; i++)if(sum[i]==k)return true;
	for(int i=begin[numr]; i<=r; i++)if(sum[i]==k)return true;
	for(int i=numl+1; i<numr; i++) {
		int z=s[lower_bound(s+begin[i]+1,s+end[i]+1,k)-s];
		if(z==k)return true;
	}
	return false;
}
bool find2(int x,int y,int k) {
	while(top[y]!=top[x]) {
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		if(find1(p[top[x]],p[x],k))return true;
		x=f[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return find1(p[x],p[y],k);
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++)scanf("%d",&a[i]);
	for(int i=1; i<n; i++) {
		scanf("%d%d",&u,&v);
		ve[u].push_back(v);
		ve[v].push_back(u);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	build();
	int x,y,z;
	while(m--) {
		scanf("%d%d%d",&x,&y,&z);
		if(find2(x,y,z))printf("1");
		else printf("0");
	}
}