#include <cstdio> #include <vector> #include <deque> char STR[100100]; bool init[100100]; bool final[100100]; std::vector<int> neighbors[100100]; int getNext(int v, int p) { if (neighbors[v].size() > 2) { return -1; } for (int n : neighbors[v]) { if (n!=p) return n; } return -1; } bool check(const std::deque<int> ¤t, const std::deque<int> &target) { int pos = 0; for (int n : target) { while (current[pos] != n) { pos++; if (pos >= current.size()) { return false; } } } return true; } int main() { int K; scanf("%d", &K); while (K--) { int N; bool has_zero = false; bool has_one = false; bool needs_zero = false; bool needs_one = false; int end_node = -1; bool same = true; scanf("%d\n%s\n", &N, STR); for (int i=1; i<=N; ++i) { init[i] = (STR[i-1]=='1'); neighbors[i].clear(); has_zero = has_zero || !init[i]; has_one = has_one || init[i]; } scanf("%s", STR); for (int i=1; i<=N; ++i) { final[i] = (STR[i-1]=='1'); needs_zero = needs_zero || !final[i]; needs_one = needs_one || final[i]; same = same && (final[i] == init[i]); } for (int i=0; i<N-1; i++) { int a,b; scanf("%d %d", &a, &b); neighbors[a].push_back(b); neighbors[b].push_back(a); } if ((!has_zero && !needs_zero) || (!has_one && !needs_one) || same) { printf("TAK\n"); continue; } if ((!has_zero && needs_zero) || (!has_one && needs_one)) { printf("NIE\n"); continue; } //check nodes wigh degree >= 3 bool no_super = true; bool has_big = false; for (int i=1; i<=N; ++i) { for (int node: neighbors[i]) { no_super = no_super && (final[i] != final[node]); } if (neighbors[i].size() == 1) { end_node = i; } else if (neighbors[i].size() >= 3) { has_big = true; } } if (has_big) { if (!no_super) { printf("TAK\n"); } else { printf("NIE\n"); } } else { std::deque<int> current, target; int prev = -1; int next = -1; int node = end_node; current.push_back(init[node]); target.push_back(final[node]); while ((next = getNext(node, prev)) != -1) { current.push_back(init[next]); target.push_back(final[next]); prev = node; node = next; } if (!check(current, target)) { printf("NIE\n"); } else { printf("TAK\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 | #include <cstdio> #include <vector> #include <deque> char STR[100100]; bool init[100100]; bool final[100100]; std::vector<int> neighbors[100100]; int getNext(int v, int p) { if (neighbors[v].size() > 2) { return -1; } for (int n : neighbors[v]) { if (n!=p) return n; } return -1; } bool check(const std::deque<int> ¤t, const std::deque<int> &target) { int pos = 0; for (int n : target) { while (current[pos] != n) { pos++; if (pos >= current.size()) { return false; } } } return true; } int main() { int K; scanf("%d", &K); while (K--) { int N; bool has_zero = false; bool has_one = false; bool needs_zero = false; bool needs_one = false; int end_node = -1; bool same = true; scanf("%d\n%s\n", &N, STR); for (int i=1; i<=N; ++i) { init[i] = (STR[i-1]=='1'); neighbors[i].clear(); has_zero = has_zero || !init[i]; has_one = has_one || init[i]; } scanf("%s", STR); for (int i=1; i<=N; ++i) { final[i] = (STR[i-1]=='1'); needs_zero = needs_zero || !final[i]; needs_one = needs_one || final[i]; same = same && (final[i] == init[i]); } for (int i=0; i<N-1; i++) { int a,b; scanf("%d %d", &a, &b); neighbors[a].push_back(b); neighbors[b].push_back(a); } if ((!has_zero && !needs_zero) || (!has_one && !needs_one) || same) { printf("TAK\n"); continue; } if ((!has_zero && needs_zero) || (!has_one && needs_one)) { printf("NIE\n"); continue; } //check nodes wigh degree >= 3 bool no_super = true; bool has_big = false; for (int i=1; i<=N; ++i) { for (int node: neighbors[i]) { no_super = no_super && (final[i] != final[node]); } if (neighbors[i].size() == 1) { end_node = i; } else if (neighbors[i].size() >= 3) { has_big = true; } } if (has_big) { if (!no_super) { printf("TAK\n"); } else { printf("NIE\n"); } } else { std::deque<int> current, target; int prev = -1; int next = -1; int node = end_node; current.push_back(init[node]); target.push_back(final[node]); while ((next = getNext(node, prev)) != -1) { current.push_back(init[next]); target.push_back(final[next]); prev = node; node = next; } if (!check(current, target)) { printf("NIE\n"); } else { printf("TAK\n"); } } } return 0; } |