真的要崩溃了。虽然知道应该不会有人帮我看的，但还是试试吧。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cassert>
using namespace std;
const int N = 1e5 + 10, M = N << 1;
int e[M], h[N], nxt[M], idx = 1;
int in[N], out[N], id[N << 1], dfn;
int dep[N], fa[N][22], ht[2], v[N], bsz;
bool ans[N], vis[N << 1];

int n, m;
struct query_t {
    int l, r, id;
    bool t;
    bool operator<(const query_t& rhs) const {
        return l / bsz != rhs.l / bsz ? l < rhs.l : (l / bsz & 1) ? r < rhs.r : r > rhs.r;
    }
} q[M];

void add(int a, int b) {
    e[idx] = b, nxt[idx] = h[a], h[a] = idx++;
}

void add(int x) {
    if (vis[x])
        ht[v[x]]--;
    else
        ht[v[x]]++;
    vis[x] ^= 1;
}

void dfs(int u, int pa) {
    id[in[u] = ++dfn] = u;
    dep[u] = dep[pa] + 1;
    fa[u][0] = pa;
    for (int i = h[u]; i; i = nxt[i]) {
        int son = e[i];
        if (son == pa)
            continue;
        dfs(son, u);
    }
    id[out[u] = ++dfn] = u;
}

int lca(int x, int y) {
    if (dep[x] > dep[y])
        swap(x, y);
    for (int i = 20; i + 1; i--) {
        if (dep[y] - (1 << i) >= dep[x])
            y = fa[y][i];
    }
    if (x == y)
        return x;
    for (int i = 20; i + 1; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
int main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    //freopen("a.out", "w", stdout);
#else
    cin.tie(0)->sync_with_stdio(0);
#endif
    cin >> n >> m;
    bsz = sqrt(n << 1);
    for (int i = 1; i <= n; ++i) {
        char ch;
        cin >> ch;
        v[i] = ch == 'H';
    }
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1, 0);
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    for (int i = 1; i <= m; i++) {
        int a, b;
        char t;
        cin >> a >> b >> t;
        if (in[a] > in[b])
            swap(a, b);
        
        int l = lca(a, b) == a ? in[a] : out[a];
        int r = in[b];
        
        
        q[i] = { l, r, i, t == 'H' };/*
        if (i==693) {
            printf("%d %d %c\n", l, r, t);
        }*/
    }
    sort(q + 1, q + 1 + m);
    int l = 1, r = 0;
    for (int i = 1; i <= m; ++i) {
        /*if (q[i].id == 693) {
            printf("%d %d\n",q[i].l, q[i].r);
            for(int j=q[i].l;j<=q[i].r;++j)
            printf("%c", v[id[j]] ? 'H' :'G');
            printf("\nl: %d r:%d\nht[G H]: %d %d\n", l,r,ht[0],ht[1]);
        }*/
        while (r < q[i].r)
            add(id[++r]);
        while (l > q[i].l)
            add(id[--l]);
        while (r > q[i].r)
            add(id[r--]);
        while (l < q[i].l)
            add(id[l++]);
        
        ans[q[i].id] = ht[q[i].t];
    }
    for (int i = 1; i <= m; ++i)
        cout << ans[i];
    //    puts("");
    //cout<<ans[693];
}