#include <cstdio> #include <vector> const int max_n = 100010; std::vector<int> T[max_n]; char current[max_n]; char expected[max_n]; int n; int cn, en; int curr_pattern[max_n]; int exp_pattern[max_n]; void process_path(int v, int u) { if (current[v] - '0' != curr_pattern[cn - 1]) { curr_pattern[cn++] = current[v] - '0'; } if (expected[v] - '0' != exp_pattern[en - 1]) { exp_pattern[en++] = expected[v] - '0'; } for (int i = 0; i < T[v].size(); ++i) { if (T[v][i] != u) process_path(T[v][i], v); } } bool good_path(int v, int u, char prev) { // printf("%d %d %c %c\n", v + 1, u + 1, expected[v], prev); if (expected[v] == prev) return true; if (T[v].size() == 1 || T[v].size() > 2) return false; for (int i = 0; i < T[v].size(); ++i) { if (T[v][i] != u) return good_path(T[v][i], v, expected[v]); } // should never happen. return false; } bool gogo() { scanf("%d", &n); for (int i = 0; i < n; ++i) T[i].clear(); scanf(" %s ", current); scanf(" %s ", expected); for (int i = 1; i < n; ++i) { int u, v; scanf("%d %d", &u, &v); --u, --v; T[v].push_back(u); T[u].push_back(v); } // expected == current int same_positions = 0; for (int i = 0; i < n; ++i) { same_positions += expected[i] == current[i]; } if (same_positions == n) return true; int curr_cnt_1 = 0, exp_cnt_1 = 0; for (int i = 0; i < n; ++i) { curr_cnt_1 += current[i] - '0'; exp_cnt_1 += expected[i] - '0'; } // unicolor starting point if (curr_cnt_1 == n || curr_cnt_1 == 0) { // return true iff the same unicolor at the end. return curr_cnt_1 == exp_cnt_1; } bool not_path = false; for (int i = 0; i < n; ++i) { if (T[i].size() >= 3) { not_path = true; // star case. for (int j = 0; j < T[i].size(); ++j) { // has child with the same color, easy case. if (expected[i] == expected[T[i][j]]) return true; } for (int j = 0; j < T[i].size(); ++j) { if (good_path(T[i][j], i, expected[i])) return true; } } } if (not_path) return false; // single path case. for (int i = 0; i < n; ++i) { if (T[i].size() == 1) { cn = en = 1; curr_pattern[0] = current[i] - '0'; exp_pattern[0] = expected[i] - '0'; process_path(i, i); if (curr_pattern[0] == exp_pattern[0]) return en <= cn; return en < cn; } } // should never happen. return false; } int main() { int tests; scanf("%d", &tests); while (tests--) printf("%s\n", gogo() ? "TAK" : "NIE"); 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 | #include <cstdio> #include <vector> const int max_n = 100010; std::vector<int> T[max_n]; char current[max_n]; char expected[max_n]; int n; int cn, en; int curr_pattern[max_n]; int exp_pattern[max_n]; void process_path(int v, int u) { if (current[v] - '0' != curr_pattern[cn - 1]) { curr_pattern[cn++] = current[v] - '0'; } if (expected[v] - '0' != exp_pattern[en - 1]) { exp_pattern[en++] = expected[v] - '0'; } for (int i = 0; i < T[v].size(); ++i) { if (T[v][i] != u) process_path(T[v][i], v); } } bool good_path(int v, int u, char prev) { // printf("%d %d %c %c\n", v + 1, u + 1, expected[v], prev); if (expected[v] == prev) return true; if (T[v].size() == 1 || T[v].size() > 2) return false; for (int i = 0; i < T[v].size(); ++i) { if (T[v][i] != u) return good_path(T[v][i], v, expected[v]); } // should never happen. return false; } bool gogo() { scanf("%d", &n); for (int i = 0; i < n; ++i) T[i].clear(); scanf(" %s ", current); scanf(" %s ", expected); for (int i = 1; i < n; ++i) { int u, v; scanf("%d %d", &u, &v); --u, --v; T[v].push_back(u); T[u].push_back(v); } // expected == current int same_positions = 0; for (int i = 0; i < n; ++i) { same_positions += expected[i] == current[i]; } if (same_positions == n) return true; int curr_cnt_1 = 0, exp_cnt_1 = 0; for (int i = 0; i < n; ++i) { curr_cnt_1 += current[i] - '0'; exp_cnt_1 += expected[i] - '0'; } // unicolor starting point if (curr_cnt_1 == n || curr_cnt_1 == 0) { // return true iff the same unicolor at the end. return curr_cnt_1 == exp_cnt_1; } bool not_path = false; for (int i = 0; i < n; ++i) { if (T[i].size() >= 3) { not_path = true; // star case. for (int j = 0; j < T[i].size(); ++j) { // has child with the same color, easy case. if (expected[i] == expected[T[i][j]]) return true; } for (int j = 0; j < T[i].size(); ++j) { if (good_path(T[i][j], i, expected[i])) return true; } } } if (not_path) return false; // single path case. for (int i = 0; i < n; ++i) { if (T[i].size() == 1) { cn = en = 1; curr_pattern[0] = current[i] - '0'; exp_pattern[0] = expected[i] - '0'; process_path(i, i); if (curr_pattern[0] == exp_pattern[0]) return en <= cn; return en < cn; } } // should never happen. return false; } int main() { int tests; scanf("%d", &tests); while (tests--) printf("%s\n", gogo() ? "TAK" : "NIE"); return 0; } |