#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=5e5+555,M=1e6+555;
char c;string st;
int head[N],ver[M],Next[M],d[N],f[N][155],dish[N],disg[N],v[N],h[N],g[N],MAX,n,m,s,tot,root;
queue <int> q;
void add(int x,int y)
{
	ver[++tot]=y;
	Next[tot]=head[x];
	head[x]=tot;
} 
void bfs(int k)
{
	q.push(k),d[k]=1;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=Next[i])
		{
			int y=ver[i];
			if(d[y])
				continue;
			d[y]=d[x]+1; // d[x] 存 s 到 x 的距离
			dish[y]=dish[x]+h[y],disg[y]=disg[x]+g[y];
			f[y][0]=x; // f[y][i] 表示 y 的 2^i 辈祖先
			for(int j=1;j<=MAX;j++)
				f[y][j]=f[f[y][j-1]][j-1]; // 2^(j-1)*(j-1)=2^j
			q.push(y);
		}
	}
}
int LCA(int x,int y)
{
	if(d[x]>d[y])
		return LCA(y,x);
	for(int i=MAX;i>=0;i--)
		if(d[f[y][i]]>=d[x])
			y=f[y][i]; // 将 y 和 x 的深度对齐
	if(x==y)
		return x; // 若已经找到了 lca(x,y) 
	for(int i=MAX;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i]; // 这时候 x(或y) 的父节点就是 lca(x.y)
	return f[x][0];
}
int main()
{
//	freopen("wdnmd.in","r",stdin);
//	freopen("wdnmd.out","w",stdout);
	scanf("%d %d",&n,&m);
	getline(cin,st);
	MAX=(int)(log(n)/log(2))+1; // MAX 是最多能走的步数
	for(int i=1;i<=n;i++)
	{
		c=getchar();
		if(c=='H') h[i]=1;
			else g[i]=1;
	}
	for(int i=1,x,y;i<n;i++)
		scanf("%d %d",&x,&y),add(x,y),add(y,x),v[y]=1;
	for(int i=1;i<=n && !root ;i++)
		if(!v[i]) root=i;
	bfs(root);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d %d %c",&x,&y,&c);
		int z=LCA(x,y);
		if(c=='H')
		{
			if(dish[x]+dish[y]-2*dish[z]>=1) printf("1");
				else printf("0");
		}
		else
		{
			if(disg[x]+disg[y]-2*disg[z]>=1) printf("1");
				else printf("0");
		}
	}
	return 0;
}

树上倍增求 LCA

$RT$