題目描述

Farmer John 計劃建造 N（1≤N≤10^5）個農場，用 N?1 條道路連接，構成一棵樹（也就是說，所有農場之間都互相可以到達，并且沒有環）。每個農場有一頭奶牛，品種為更賽牛或荷斯坦牛之一。

Farmer John 的 M 個朋友（1≤M≤10^5）經常前來拜訪他。在朋友 i 拜訪之時，Farmer John 會與他的朋友沿著從農場 Ai 到農場 Bi 之間的唯一路徑行走（可能有 Ai=Bi）。除此之外，他們還可以品嘗他們經過的路徑上任意一頭奶牛的牛奶。由于 Farmer John 的朋友們大多數也是農場主，他們對牛奶有著極強的偏好。他的有些朋友只喝更賽牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他們訪問時能喝到他們偏好的牛奶才會高興。

請求出每個朋友在拜訪過后是否會高興。

輸入格式

輸入的第一行包含兩個整數 N 和 M。 第二行包含一個長為 N 的字符串。如果第 i 個農場中的奶牛是更賽牛，則字符串中第 i 個字符為 'G'，如果第 i 個農場中的奶牛是荷斯坦牛則為 'H'。 以下 N?1 行，每行包含兩個不同的整數 X 和 Y（1≤X,Y≤N），表示農場 X 與 Y 之間有一條道路。 以下 M 行，每行包含整數 Ai，Bi，以及一個字符 Ci。Ai 和 Bi 表示朋友 i 拜訪時行走的路徑的端點，Ci 是 'G' 或 'H' 之一，表示第 i 個朋友喜歡更賽牛的牛奶或是荷斯坦牛的牛奶。

輸出格式

輸出一個長為 M 的二進制字符串。如果第 i 個朋友會感到高興，則字符串的第 i 個字符為 '1'，否則為 '0'。

樣例輸入

5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H

樣例輸出

10110

提示

在這里，從農場 1 到農場 4 的路徑包括農場 1、2 和 4。所有這些農場里都是荷斯坦牛，所以第一個朋友會感到滿意，而第二個朋友不會。 測試點 2-5 滿足 N≤10^3,M≤2?10^3。

?思路

運用并查集，將相連的且有相同種類的農場并在一起。

判斷時有三種情況：

1.起點和終點不在同一集合，說明路上一定會有兩種奶牛，記為'1'；

2.起點和終點在同一集合，且奶牛種類為朋友要求的，記為'1'；

3.起點和終點在同一集合，但奶牛種類不是朋友要求的，記為'0'。

代碼（可自行優化）

#include<bits/stdc++.h>
using namespace std;
int n, m, u, v,num=0;
int father[100100];
char q[100100],p[100100];int find(int t) {if (father[t] != t) {father[t] = find(father[t]);}return father[t];
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {cin >> q[i];}for (int i = 1; i <= n; i++) {father[i] = i;}for (int i = 1; i < n; i++) {scanf("%d%d", &u, &v);if (q[u] == q[v]) {if (find(u) != find(v)) {father[find(u)] = find(v);}}}for (int i = 1; i <= m; i++) {int a, b;char c;scanf("%d%d", &a, &b);cin>>c;if (find(a) != find(b)) p[num]='1',num++;else {if (q[find(a)] == c) p[num]='1',num++;else p[num]='0',num++;}} for(int i=0;i<num;i++) cout<<p[i];return 0;
}