#include <iostream> #include <vector> #include <string> using namespace std; int n, a, b; string s1, s2; vector<int> v[100001]; int debug = 0; int test() { cin >> n >> s1 >> s2; int sarowne = 0; for (int i = 1; i <= n; i++) v[i].clear(); for (int i = 1; i < n; i++) { cin >> a >> b; v[a].push_back(b); v[b].push_back(a); if (s2[a-1] == s2[b-1]) sarowne = 1; } if (n == 1) return s1 == s2; if (s1 == s2) return 1; if (!sarowne) return 0; int start = 0; for (int i = 1; i <= n; i++) { if (v[i].size() > 2) goto trzy; if (v[i].size() == 1) start = i; } { int prev = 0; string n1, n2; n1 += s1[start-1]; n2 += s2[start-1]; while (1) { if (v[start].size() == 1 && prev != 0) break; if (v[start][0] == prev) prev = start, start = v[start][1]; else prev = start, start = v[start][0]; if (s1[start-1] != n1.back()) n1 += s1[start-1]; if (s2[start-1] != n2.back()) n2 += s2[start-1]; } if (n1.length() > n2.length()) return 1; if (n1 == n2) return 1; return 0; } trzy: int jestzero=0, jestjeden=0, mabyczero=0, mabycjeden = 0; for (int i = 0; i < n; i++) { if (s1[i] == '0') jestzero = 1; else jestjeden = 1; if (s2[i] == '0') mabyczero = 1; else mabycjeden = 1; } if (!jestzero && mabyczero) return 0; if (!jestjeden && mabycjeden) return 0; return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { if (test()) cout << "TAK\n"; else cout << "NIE\n"; } }
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 | #include <iostream> #include <vector> #include <string> using namespace std; int n, a, b; string s1, s2; vector<int> v[100001]; int debug = 0; int test() { cin >> n >> s1 >> s2; int sarowne = 0; for (int i = 1; i <= n; i++) v[i].clear(); for (int i = 1; i < n; i++) { cin >> a >> b; v[a].push_back(b); v[b].push_back(a); if (s2[a-1] == s2[b-1]) sarowne = 1; } if (n == 1) return s1 == s2; if (s1 == s2) return 1; if (!sarowne) return 0; int start = 0; for (int i = 1; i <= n; i++) { if (v[i].size() > 2) goto trzy; if (v[i].size() == 1) start = i; } { int prev = 0; string n1, n2; n1 += s1[start-1]; n2 += s2[start-1]; while (1) { if (v[start].size() == 1 && prev != 0) break; if (v[start][0] == prev) prev = start, start = v[start][1]; else prev = start, start = v[start][0]; if (s1[start-1] != n1.back()) n1 += s1[start-1]; if (s2[start-1] != n2.back()) n2 += s2[start-1]; } if (n1.length() > n2.length()) return 1; if (n1 == n2) return 1; return 0; } trzy: int jestzero=0, jestjeden=0, mabyczero=0, mabycjeden = 0; for (int i = 0; i < n; i++) { if (s1[i] == '0') jestzero = 1; else jestjeden = 1; if (s2[i] == '0') mabyczero = 1; else mabycjeden = 1; } if (!jestzero && mabyczero) return 0; if (!jestjeden && mabycjeden) return 0; return 1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { if (test()) cout << "TAK\n"; else cout << "NIE\n"; } } |