fa[i][j]表示i的2的j次方祖先

d[i]表示i的深度

dis[i][j]表示从i到2的j次方祖先有哪种奶牛（01为G,10为H，11为GH）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#define fu(i,a,b) for (int i = a; i <= b; i++)
#define fd(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef bool bl;
typedef long long ll;
typedef double db;
vector <int> v[100001];
int n, m;
int x, y;
int fa[100001][21];
int d[100001];
char s[100001];
char o;
int dis[100001][21];
void dfs(int u, int f,int de) {
	fa[u][0] = f;
	d[u] = de;
	dis[u][0] |= dis[f][0];
	fu(i, 1, 20) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
		dis[u][i] = dis[u][i-1] | dis[fa[u][i - 1]][i - 1];
	}
	fu(i, 0, v[u].size() - 1) {
		if (v[u][i] != f) {
			dfs(v[u][i], u,de+1);
		}
	}
	return;
}
int lca(int x, int y, int s) {
	int ans = 0;
	if (d[x] > d[y])swap(x, y);
	fd(i, 20, 0) {
		if (d[fa[y][i]] >= d[x]) {
			ans |= dis[y][i];
			y = fa[y][i];
		}
	}
	if (x == y) {
		if ((s & ans) == s)return 1;
		else return 0;
	}
	fd(i, 20, 0) {
		if (fa[x][i] != fa[y][i]) {
			ans |= dis[x][i];
			ans |= dis[y][i];
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	ans |= dis[x][0];
	ans |= dis[x][0];
	x = fa[x][0];
	y = fa[y][0];
	if ((s & ans) == s)return 1;
	else return 0;
}
int main() {
	scanf("%d%d", &n, &m);
	scanf("%s", &s);
	fu(i, 1, n) {
		if (s[i - 1] == 'G')dis[i][0] = 1;
		else dis[i][0] = 2;
	}
	fu(i, 1, n - 1) {
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,1,1);
	fu(i, 1, m) {
		cin >> x >> y >> o;
		int u;
		if (o == 'G')u = 1;
		else u = 2;
		printf("%d", lca(x, y, u));
	}
	return 0;
}