倍增过程中这里的 fa数组可以推广一下，保存每个点往根方向的路径上各个边/点的性质。常见的维护值有路径长度（树上求最短路）以及点的特殊性质（比如本题中各个农场的奶牛种类）等。
这里维护的数组d p [ i , j , o p ] ( o p = 1 或 者 o p = 0 ) dp[i,j,op] (op=1或者op=0)dp[i,j,op](op=1或者op=0)
维护的是i 点 往 树 根 方 向 走 2 j 步 经 过 没 经 过 o p i点往树根方向走2^j步经过没经过opi点往树根方向走2j步经过没经过op
转移方程为:d p [ i , j , o p ] ∣ = ( d p [ i , j − 1 , o p ] ∣ d p [ f a [ i ] [ j − 1 ] , j − 1 , o p ] ) dp[i,j,op]|=(dp[i,j-1,op]|dp[fa[i][j-1],j-1,op])dp[i,j,op]∣=(dp[i,j−1,op]∣dp[fa[i][j−1],j−1,op])
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10, INF = 0x3f3f3f3f; vector<int>g[N]; int n, m; char s[N]; int fa[N][20]; int dep[N]; bool dp[N][20][2];//i走2^j步有没有经过1,0 转移方程 g[i,j,op]|=g[i,j-1,op]|g[fa[i,j-1],j-1,op]; int book[N]; int k; void bfs(int root) { memset(dep, 0x3f, sizeof(dep)); dep[root] = 1; dep[0] = 0; queue<int>q; q.push(root); while (q.size()) { int t = q.front(); q.pop(); for (auto x : g[t]) { if (dep[x] > dep[t] + 1) { dep[x] = dep[t] + 1; q.push(x); fa[x][0] = t; dp[x][0][book[t]] = 1; for (int i = 1; i <= k; i++) { fa[x][i] = fa[fa[x][i - 1]][i - 1]; dp[x][i][1] |= (dp[x][i - 1][1] | dp[fa[x][i - 1]][i - 1][1]); dp[x][i][0] |= (dp[x][i - 1][0] | dp[fa[x][i - 1]][i - 1][0]); } } } } } bool lca(int a, int b, bool f) { if (dep[a] < dep[b]) swap(a, b); bool res = 0; for (int i = k; i >= 0; i--) { if (dep[fa[a][i]] >= dep[b]) { res |= dp[a][i][f]; a = fa[a][i]; } } if (a == b) { return res; } for (int i = k; i >= 0; i--) { if (fa[a][i] != fa[b][i]) { res |= dp[a][i][f]; res |= dp[b][i][f]; a = fa[a][i]; b = fa[b][i]; } } res |= dp[a][0][f]; res |= dp[b][0][f]; return res; } void solve() { cin >> n >> m; cin >> s + 1; k = (int)(log(n) / log(2)) + 1; for (int i = 1; i <= n; i++) { if (s[i] == 'H') book[i] = 1; for (int j = 0; j <= k; j++) dp[i][j][book[i]] = 1; } for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } bfs(1); for (int i = 1; i <= m; i++) { int x, y; char t; bool f = 0; cin >> x >> y >> t; if (t == 'H') f = 1; if (x == y) { cout << (book[x] == f); } else { bool res = lca(x, y, f); cout << res; } } } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }
