#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 5, M = 2e5 + 5;
int h[N], e[M], ne[M], val[N], dist[N], a, p, b, n, m, idx, d, v, de[N], fa[N][18];
char ch, s[N];
bool st[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs()
{
    memset(de, 0x3f, sizeof(de));
    queue<int> q;
    de[0] = 0, de[1] = 1;
    q.push(1);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (de[j] > de[t] + 1)
            {
                de[j] = de[t] + 1, fa[j][0] = t, q.push(j);
                for (int k = 1; k <= 17; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}
void dfs(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father)
            continue;
        dist[j] = dist[u] + 1;
        val[j] += val[u];
        dfs(j, u);
    }
}
int lca(int a, int b)
{
    if (de[a] < de[b])
        swap(a, b);
    for (int k = 17; k >= 0; k--)
        if (de[fa[a][k]] >= de[b])
            a = fa[a][k];
    if (a == b)
        return a;
    for (int k = 17; k >= 0; k--)
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}
int main()
{
    memset(h, -1, sizeof(h));
    cin >> n >> m;
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++)
        st[i] = val[i] = (s[i] == 'H');
    for (int i = 1; i < n; i++)
        scanf("%d%d", &a, &b), add(a, b), add(b, a);
    bfs();
    dist[1] = 1;
    dfs(1, -1);
    while (m--)
    {
        cin >> a >> b >> ch;
        if (a == b)
        {
            if (ch == 'H')
                printf("%d", st[a]);
            else
                printf("%d", !st[a]);
            continue;
        }
        p = lca(a, b);
        d = dist[a] + dist[b] - 2 * dist[p];
        v = val[a] + val[b] - 2 * val[p];
        if (ch == 'H')
        {
            if (v > 0)
                printf("%d", 1);
            else
                printf("%d", 0);
        }
        else
        {
            if (v < d)
                printf("%d", 1);
            else
                printf("%d", 0);
        }
    }
    puts("");
}

52pts，还行，比我预想的火烧云强（

下了一个数据看了一下第一行的输出，是一样的，大概是那些细节出了问题吧，求大佬们帮忙找一找，蒟蒻刚写的第一道题，LCA没什么debug能力啊...