#include <bits/stdc++.h> using namespace std; constexpr int MAXN = 100008; char in[MAXN], out[MAXN]; struct Test { int n; bool bipartite = true; bool is_deg3 = false; vector<vector<int>> g; void Add(int a, int b) { is_deg3 |= g[a].size() >= 2; if (is_deg3) return; g[a].push_back(b); } void Result(bool yes) { printf(yes ? "TAK\n" : "NIE\n"); } int CountBlocks(const vector<int>& p, char *s) { int count = 1; for (int i = 1; i < n; ++i) count += s[p[i - 1]] != s[p[i]]; return count; } bool SingleColor() { for (int i = 1; i < n; ++i) if (in[i] != in[i - 1]) return false; return true; } Test() { Run(); } void Run() { scanf("%d%s%s", &n, in, out); g.resize(n); for (int i = 1; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); a--; b--; bipartite &= out[a] != out[b]; Add(a, b); Add(b, a); } if (strcmp(in, out) == 0) return Result(true); if (n == 1) return Result(false); if (SingleColor()) return Result(false); if (is_deg3) return Result(!bipartite); int a; for (a = 0; g[a].size() != 1; ++a); vector<int> p(1, a); for (int i = 1; i < n; ++i) { if (i == 1) a = g[a][0]; else a = g[a][0] ^ g[a][1] ^ p[i - 2]; p.push_back(a); } int in_blocks = CountBlocks(p, in); int out_blocks = CountBlocks(p, out); Result(in_blocks > out_blocks || in_blocks == out_blocks && in[p[0]] == out[p[0]]); } }; int main() { int tests; scanf("%d", &tests); for (; tests; tests--) Test(); 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 | #include <bits/stdc++.h> using namespace std; constexpr int MAXN = 100008; char in[MAXN], out[MAXN]; struct Test { int n; bool bipartite = true; bool is_deg3 = false; vector<vector<int>> g; void Add(int a, int b) { is_deg3 |= g[a].size() >= 2; if (is_deg3) return; g[a].push_back(b); } void Result(bool yes) { printf(yes ? "TAK\n" : "NIE\n"); } int CountBlocks(const vector<int>& p, char *s) { int count = 1; for (int i = 1; i < n; ++i) count += s[p[i - 1]] != s[p[i]]; return count; } bool SingleColor() { for (int i = 1; i < n; ++i) if (in[i] != in[i - 1]) return false; return true; } Test() { Run(); } void Run() { scanf("%d%s%s", &n, in, out); g.resize(n); for (int i = 1; i < n; ++i) { int a, b; scanf("%d%d", &a, &b); a--; b--; bipartite &= out[a] != out[b]; Add(a, b); Add(b, a); } if (strcmp(in, out) == 0) return Result(true); if (n == 1) return Result(false); if (SingleColor()) return Result(false); if (is_deg3) return Result(!bipartite); int a; for (a = 0; g[a].size() != 1; ++a); vector<int> p(1, a); for (int i = 1; i < n; ++i) { if (i == 1) a = g[a][0]; else a = g[a][0] ^ g[a][1] ^ p[i - 2]; p.push_back(a); } int in_blocks = CountBlocks(p, in); int out_blocks = CountBlocks(p, out); Result(in_blocks > out_blocks || in_blocks == out_blocks && in[p[0]] == out[p[0]]); } }; int main() { int tests; scanf("%d", &tests); for (; tests; tests--) Test(); return 0; } |