倍增LCA：$8$ 分

设定 $root$ 为 $1$

$num[x][0]$ 代表从 $x$ 到 $1$ 的 $G$ 个数

$num[x][1]$ 代表从 $x$ 到 $1$ 的 $H$ 个数

最后前缀和一下

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n,m,uu,vv;
string a,ans;
char c;
int num[MAXN][2];
vector<int>v[MAXN];
void add(int x,int y){
	v[x].push_back(y);
	v[y].push_back(x);
}
int fa[MAXN][22],depth[MAXN],lg[MAXN];
int dfs(int x,int fath){
	depth[x]=depth[fath]+1;
	fa[x][0]=fath;
	
	if(a[x]=='G')num[x][0]=1;
	else num[x][1]=1;
	num[x][0]+=num[fath][0];
	num[x][1]+=num[fath][1];
	
	for(int i=1;i<=lg[depth[i]];++i){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=0;i<v[x].size();++i){
		if(v[x][i]!=fath)dfs(v[x][i],x);
	}
}
int LCA(int x,int y){
	if(depth[x]<depth[y])swap(x,y);
	while(depth[x]>depth[y]){
		x=fa[x][lg[depth[x]-depth[y]]-1];
	}
	if(x==y)return x;
	for(int k=lg[depth[x]]-1;k>=0;--k){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k],y=fa[y][k];
		}
	}
	return fa[x][0];
}
int main(){
	cin>>n>>m>>a;a=' '+a;
	for(int i=1;i<n;++i){
		cin>>uu>>vv;
		add(uu,vv);
	}
	for(int i=1;i<=n;++i){
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	}
	dfs(1,0);
	int numm=0;
	for(int i=1;i<=m;++i){
		cin>>uu>>vv>>c;
		int lca=LCA(uu,vv);
		if(c=='G'){
		    if(num[uu][0]+num[vv][0]-2*num[lca][0]+(a[lca]=='G')>0)ans[i]='1';
		    else ans[i]='0';
		}else{
		    if(num[uu][1]+num[vv][1]-2*num[lca][1]+(a[lca]=='H')>0)ans[i]='1';
		    else ans[i]='0';
		}
	}
	for(int i=1;i<=m;++i)cout<<ans[i];
	return 0;
}