WA ON Test#9。https://www.luogu.com.cn/record/227408998

#include<map>

#include<bits/stdc++.h>

#define str string
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)

using namespace std;
typedef long long LL;
const LL MAXN = 1e5 * 2;

LL cnt = 0, to[MAXN], net[MAXN], head[MAXN];
LL fa[MAXN], deep[MAXN], n, m, Q, f[MAXN];
LL ans = 0, size[MAXN], son[MAXN], id[MAXN], tot = 0, top[MAXN];
str S;
LL disG[MAXN], disH[MAXN]; 
struct Milk {
	LL A, B;
	str C;
}x[MAXN];
void addedge(LL u, LL v) {
	to[++cnt] = v; net[cnt] = head[u]; head[u] = cnt;
}
void dfs1(LL now, LL fax, LL dep) {
	fa[now] = fax; deep[now] = dep; size[now] = 1;
	disH[now] = disH[fax];
	disG[now] = disG[fax];
	if(S[now - 1] == 'H') disH[now]++;
	else if(S[now - 1] == 'G') disG[now]++;
	LL maxson = -1;
	for(LL i = head[now]; i; i = net[i]) {
		if(to[i] != fax) {
			dfs1(to[i], now, dep + 1);
			size[now] += size[to[i]];
			if(maxson < size[to[i]]) {
				son[now] = to[i];
				maxson = size[to[i]];
			}

		}
	}
}
void dfs2(LL now, LL topx) {
	id[now] = ++tot;
	top[now] = topx;
	if(!son[now]) return ;
	dfs2(son[now], topx);
	for(LL i = head[now]; i; i = net[i]) 
		if(!id[to[i]]) dfs2(to[i], to[i]);
}
LL LCA(LL u, LL v) {
	while(top[u] != top[v]) {
		if(deep[top[u]] < deep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	return deep[u] < deep[v] ? u : v;
}
vector<LL> edge[MAXN]; 
int main() {
	scanf("%lld%lld", &n, &m);
	cin >> S;
	rep(i, 1, n - 1) {
		LL u, v; scanf("%lld%lld", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	scanf("%lld", &Q);
	dfs1(1, 0, 0);
	dfs2(1, 1);
	str cun = "";
	rep(i, 1, m) {
		scanf("%lld%lld", &x[i].A, &x[i].B);
		cin >> x[i].C;
		LL sum = 0;
		if(x[i].C[0] == 'H') sum = disH[x[i].A] + disH[x[i].B] - disH[LCA(x[i].A, x[i].B)] - disH[fa[LCA(x[i].A, x[i].B)]];
		else if(x[i].C[0] == 'G') sum = disG[x[i].A] + disG[x[i].B] - disG[LCA(x[i].A, x[i].B)] - disG[fa[LCA(x[i].A, x[i].B)]];
		if(sum) cun += '1';
		else cun += '0';
	}
	cout << cun << '\n';
	// printf("\n");
	return 0;
}