P5836 [USACO19DEC]Milk Visits S

#include <iostream> #include <vector> #include <stack> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <cstring> #include <unordered_map> #include <unordered_set> #include <algorithm> #include <numeric> #include <chrono> #include <ctime> #include <cmath> #include <cctype> #include <string> #include <cstdio> #include <iomanip> #include <thread> #include <mutex> #include <condition_variable> #include <functional> #include <iterator> using namespace std; char color[100005]; int arr[100005]; int GetFather(int a) { int t = a; while (a != arr[a]) a = arr[a]; while (t != a) { int temp = t; t = arr[t]; arr[temp] = a; } return a; } void AddOne(int a, int b) { int fa = GetFather(a); int fb = GetFather(b); if (fa != fb) arr[fa] = arr[fb]; } int main() { string ret = ""; int n, m,a , b; char ch; cin >> n >> m; for (int i = 1; i <= n; ++i) arr[i] = i; for (int i = 1; i <= n; ++i) { cin >> color[i]; } for (int i = 1; i < n; ++i) { cin >> a >> b; if (color[a] == color[b]) AddOne(a, b); } for (int i = 0; i < m; ++i) { cin >> a >> b >> ch; if (color[a] == ch || color[b] == ch || GetFather(a) != GetFather(b)) ret.push_back('1'); else ret.push_back('0'); } cout << ret << endl; return 0; }