我的另外的解
其实只要并查集维护成森林每个树都是单色的，同色有边就连在一个连通集里面，查询时，如果两个点在同一个树，而且树颜色符合查询的颜色，或者两个点不在同一个树上，必定是经过了查询的颜色的
/********************************************************************* 程序名: 版权: Joecai 作者: Joecai 日期: 2022-05-04 21:00 说明: *********************************************************************/ #include <bits/stdc++.h> using namespace std; #define x first #define y second # define rep(i,be,en) for(int i=be;i<=en;i++) # define pre(i,be,en) for(int i=be;i>=en;i--) #define ll long long #define endl "\n" #define LOCAL #define pb push_back #define int long long typedef pair<ll, ll> PII; #define eb emplace_back #define sp(i) setprecision(i) const int N = 2e5 + 10, INF = 0x3f3f3f3f; int fa[N]; int rank[N]; char s[N]; int n, m; int col[N]; int find(int x) { if (fa[x] == x) return x; return fa[x] = find(find(fa[x])); } void solve() { cin >> n >> m; cin >> s + 1; for (int i = 1; i <= n; i++) { fa[i] = i; if (s[i] == 'H') col[i] = 1; } for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; if (col[x] == col[y]) { x = find(x); y = find(y); fa[x] = y; } } for (int i = 1; i <= m; i++) { int x, y; char t; int f = 0; cin >> x >> y >> t; if (t == 'H') f = 1; if (find(x) == find(y) && col[x] == f || find(x) != find(y)) { cout << 1; } else cout << 0; } cout << endl; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); //#ifdef LOCAL //freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); //#endif int __ = 1; //cin>>__; while (__--) { solve(); } return 0; }
