#include <iostream> #include <vector> #include <utility> typedef std::vector<int> vi; const int N = 100005; int q; int n; std::string c1; std::string c2; vi edges[N]; void input() { std::cin >> n; std::cin >> c1 >> c2; int u, v; for (int i = 0; i < n; i++) { edges[i].clear(); } for (int i = 0; i < n - 1; i++) { std::cin >> u >> v; u--; v--; edges[u].push_back(v); edges[v].push_back(u); } } int max(int a, int b) { return a > b ? a : b; } bool is_line() { for (int i = 0; i < n; i++) { if (edges[i].size() > 2) { return false; } } return true; } bool same() { return c1 == c2; } bool is_correct_line() { int u = 0; for (int i = 0; i < n; i++) { if (edges[i].size() == 1) { u = i; break; } } std::string s1 = "", s2 = ""; s1 += c1[u]; s2 += c2[u]; // std::cout << s1 << " " << s2 << "\n"; int v = (u == edges[u][0] ? edges[u][1] : edges[u][0]); // std::cout << "u " << u << " v " << v << "\n"; while (edges[v].size() > 1) { int v2 = (u == edges[v][0] ? edges[v][1] : edges[v][0]); u = v; v = v2; if (c1[u] != s1[s1.length() - 1]) { s1 += c1[u]; } if (c2[u] != s2[s2.length() - 1]) { s2 += c2[u]; } // std::cout << s1 << " " << s2 << "\n"; // std::cout << "u " << u << " v " << v << "\n"; } if (c1[v] != s1[s1.length() - 1]) { s1 += c1[v]; } if (c2[v] != s2[s2.length() - 1]) { s2 += c2[v]; } // std::cout << s1 << " " << s2 << "\n"; return s1.find(s2) != std::string::npos; } bool has_both_colors(std::string & s) { return s.find('0') != std::string::npos && s.find('1') != std::string::npos; } bool neightbour_same_color() { for (int u = 0; u < n; u++) { for (auto v : edges[u]) { if (c2[u] == c2[v]) { return true; } } } return false; } bool solve() { // std::cout << q << "\n"; if (same()) { return true; } if (!has_both_colors(c1)) { return false; } if (!neightbour_same_color()) { return false; } if (!is_line()) { // std::cout << " is not line\n"; return true; } return is_correct_line(); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> q; while (q--) { input(); std::cout << (solve() ? "TAK\n" : "NIE\n"); } return 0; }
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | #include <iostream> #include <vector> #include <utility> typedef std::vector<int> vi; const int N = 100005; int q; int n; std::string c1; std::string c2; vi edges[N]; void input() { std::cin >> n; std::cin >> c1 >> c2; int u, v; for (int i = 0; i < n; i++) { edges[i].clear(); } for (int i = 0; i < n - 1; i++) { std::cin >> u >> v; u--; v--; edges[u].push_back(v); edges[v].push_back(u); } } int max(int a, int b) { return a > b ? a : b; } bool is_line() { for (int i = 0; i < n; i++) { if (edges[i].size() > 2) { return false; } } return true; } bool same() { return c1 == c2; } bool is_correct_line() { int u = 0; for (int i = 0; i < n; i++) { if (edges[i].size() == 1) { u = i; break; } } std::string s1 = "", s2 = ""; s1 += c1[u]; s2 += c2[u]; // std::cout << s1 << " " << s2 << "\n"; int v = (u == edges[u][0] ? edges[u][1] : edges[u][0]); // std::cout << "u " << u << " v " << v << "\n"; while (edges[v].size() > 1) { int v2 = (u == edges[v][0] ? edges[v][1] : edges[v][0]); u = v; v = v2; if (c1[u] != s1[s1.length() - 1]) { s1 += c1[u]; } if (c2[u] != s2[s2.length() - 1]) { s2 += c2[u]; } // std::cout << s1 << " " << s2 << "\n"; // std::cout << "u " << u << " v " << v << "\n"; } if (c1[v] != s1[s1.length() - 1]) { s1 += c1[v]; } if (c2[v] != s2[s2.length() - 1]) { s2 += c2[v]; } // std::cout << s1 << " " << s2 << "\n"; return s1.find(s2) != std::string::npos; } bool has_both_colors(std::string & s) { return s.find('0') != std::string::npos && s.find('1') != std::string::npos; } bool neightbour_same_color() { for (int u = 0; u < n; u++) { for (auto v : edges[u]) { if (c2[u] == c2[v]) { return true; } } } return false; } bool solve() { // std::cout << q << "\n"; if (same()) { return true; } if (!has_both_colors(c1)) { return false; } if (!neightbour_same_color()) { return false; } if (!is_line()) { // std::cout << " is not line\n"; return true; } return is_correct_line(); } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cin >> q; while (q--) { input(); std::cout << (solve() ? "TAK\n" : "NIE\n"); } return 0; } |