#include <bits/stdc++.h> using namespace std; typedef long long lld; int n; string s; string t; bool isOK(vector<vector<int>> &v) { if (n == 1) return true; int start = 0, last = 0, prev = -1; for (int i = 0; i < n; ++i) { if (v[i].size() > 2) return true; if (v[i].size() == 1) { start = last; last = i; } } int counts[2] = { 0, 0 }; int countt[2] = { 0, 0 }; counts[s[start] - '0'] = 1; countt[t[start] - '0'] = 1; for (int i = start; i != last;) { for (int &j : v[i]) { if (j == prev) continue; if (s[j] != s[i]) ++counts[s[j] - '0']; if (t[j] != t[i]) ++countt[t[j] - '0']; prev = i; i = j; } } if (counts[0] < countt[0] || counts[1] < countt[1]) return true; if (counts[0] > countt[0] || counts[1] > countt[1]) return true; return s[start] == t[start]; } void solve() { cin >> n; cin >> s; cin >> t; vector<vector<int>> v(n); for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; --a, --b; v[a].push_back(b); v[b].push_back(a); } bool has[2] = { true, true }; for (char &c : t) has[c - '0'] = false; for (char &c : s) has[c - '0'] = true; if (!has[0] || !has[1]) { cout << "NIE\n"; return; } cout << (isOK(v) ? "TAK\n" : "NIE\n"); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) solve(); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <bits/stdc++.h> using namespace std; typedef long long lld; int n; string s; string t; bool isOK(vector<vector<int>> &v) { if (n == 1) return true; int start = 0, last = 0, prev = -1; for (int i = 0; i < n; ++i) { if (v[i].size() > 2) return true; if (v[i].size() == 1) { start = last; last = i; } } int counts[2] = { 0, 0 }; int countt[2] = { 0, 0 }; counts[s[start] - '0'] = 1; countt[t[start] - '0'] = 1; for (int i = start; i != last;) { for (int &j : v[i]) { if (j == prev) continue; if (s[j] != s[i]) ++counts[s[j] - '0']; if (t[j] != t[i]) ++countt[t[j] - '0']; prev = i; i = j; } } if (counts[0] < countt[0] || counts[1] < countt[1]) return true; if (counts[0] > countt[0] || counts[1] > countt[1]) return true; return s[start] == t[start]; } void solve() { cin >> n; cin >> s; cin >> t; vector<vector<int>> v(n); for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; --a, --b; v[a].push_back(b); v[b].push_back(a); } bool has[2] = { true, true }; for (char &c : t) has[c - '0'] = false; for (char &c : s) has[c - '0'] = true; if (!has[0] || !has[1]) { cout << "NIE\n"; return; } cout << (isOK(v) ? "TAK\n" : "NIE\n"); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) solve(); } |