【正经题解】Milk Visits

使用树结构表示农场之间的连接关系，保证是一棵树（没有环）。
对每个农场进行深度优先搜索（ $DFS$ ），计算每个节点到树根的距离，同时记录每个节点的更赛牛和荷斯坦牛的数量。
针对每个朋友的拜访，找到其拜访路径上的最近共同祖先，利用 $LCA$ 计算拜访路径上更赛牛和荷斯坦牛的数量。
根据朋友的牛奶偏好和拜访路径上更赛牛和荷斯坦牛的数量，判断朋友是否高兴。
将每个朋友的高兴状态记录下来，最后输出结果。

#include <bits/stdc++.h>
#define N 100005 
using namespace std;

int n, m, t, tot = 0, head[N], ver[2 * N], edge[2 * N], Next[2 * N], f[N][22], d[N], dist[N], lg[100005];
char s[100005];
int h[500005], g[500005]; // h[i]表示树根到i共有多少H g[i]同理 

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

void prework() {
    queue<int> q;
    q.push(1);
    d[1] = 1;
    if (s[0] == 'H') {
        h[1] = 1;
    } else
        g[1] = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        int i;
        for (i = head[x]; i; i = Next[i]) {
            int y = ver[i], z = edge[i];
            if (d[y])
                continue;
            d[y] = d[x] + 1;
            dist[y] = dist[x] + z;
            f[y][0] = x; // y节点的2^0倍祖先是x
            if (s[y - 1] == 'H') {
                h[y] = h[x] + 1;
                g[y] = g[x]; // 别漏下！！！ 
            } else {
                g[y] = g[x] + 1;
                h[y] = h[x];
            }
            int j;
            for (j = 1; j <= lg[d[x]]; j++) {
                f[y][j] = f[f[y][j - 1]][j - 1];
            }
            q.push(y);
        }
    }
}

int lca(int x, int y) {
    if (d[x] < d[y])
        swap(x, y); // 使得x深度较小 
    int i;
    while (d[x] > d[y]) {
        x = f[x][lg[d[x] - d[y]] - 1];
    }
    if (x == y)
        return x;
    for (i = lg[d[x]] - 1; i >= 0; i--) {
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    }
    return f[x][0];
}

int main() {
    cin >> n >> m;
    int i;
    memset(d, 0, sizeof(d));
    scanf("%s", s);
    for (i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        add(x, y, 1);
        add(y, x, 1);
    }
    for (int i = 1; i <= n + 1; ++i)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    prework();
    vector<int> v;
    for (i = 1; i <= m; i++) {
        int a, b;
        char c; //
        scanf("%d%d", &a, &b);
        scanf(" %c", &c); ///!!!!!!一定要这么写 
        int LCA = lca(a, b);
        if (c == 'H') {
            if ((h[a] + h[b] - 2 * h[LCA] + (s[LCA - 1] == 'H' ? 1 : 0)) > 0)
                v.push_back(1);
            else
                v.push_back(0);
        } else {
            if ((g[a] + g[b] - 2 * g[LCA] + (s[LCA - 1] == 'G' ? 1 : 0)) > 0)
                v.push_back(1);
            else
                v.push_back(0);
        }
    }
    for (i = 0; i < v.size(); i++)
        cout << v[i];
    return 0;
}