#include <bits/stdc++.h> using namespace std; int countChanges(vector <int> &inds, string &s) { int cnt = 0; for (int i = 0; i < (int) inds.size() - 1; i++) { cnt += s[inds[i]] != s[inds[i + 1]]; } return cnt; } bool solve(int n, vector <vector<int>> &g, string &init, string &target) { if (init == target) { return true; } vector <bool> hasColor(2, false); for (int v = 0; v < n; v++) { hasColor[init[v] - '0'] = true; } if (!hasColor[0] || !hasColor[1]) { return false; } bool bipartite = true; for (int v = 0; v < n; v++) for (int u : g[v]) { if (target[v] == target[u]) { bipartite = false; } } if (bipartite) { return false; } vector <int> leaves; for (int v = 0; v < n; v++) if (g[v].size() == 1) { leaves.push_back(v); } if (leaves.size() >= 3) { return true; } int start = leaves[0]; vector <int> path = {start, g[start][0]}; while (path.size() < n) { int last = path.back(), prv = path[path.size() - 2]; path.push_back(g[last][0] + g[last][1] - prv); } int numChangesInit = countChanges(path, init); int numChangesTarget = countChanges(path, target); if (numChangesTarget < numChangesInit) { return true; } else if (numChangesTarget > numChangesInit) { return false; } else { return init[start] == target[start]; } } int main() { ios_base::sync_with_stdio(false); int t; cin >> t; while (t--) { int n; cin >> n; string init, target; cin >> init >> target; vector <vector<int>> g(n); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } cout << (solve(n, g, init, target) ? "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 | #include <bits/stdc++.h> using namespace std; int countChanges(vector <int> &inds, string &s) { int cnt = 0; for (int i = 0; i < (int) inds.size() - 1; i++) { cnt += s[inds[i]] != s[inds[i + 1]]; } return cnt; } bool solve(int n, vector <vector<int>> &g, string &init, string &target) { if (init == target) { return true; } vector <bool> hasColor(2, false); for (int v = 0; v < n; v++) { hasColor[init[v] - '0'] = true; } if (!hasColor[0] || !hasColor[1]) { return false; } bool bipartite = true; for (int v = 0; v < n; v++) for (int u : g[v]) { if (target[v] == target[u]) { bipartite = false; } } if (bipartite) { return false; } vector <int> leaves; for (int v = 0; v < n; v++) if (g[v].size() == 1) { leaves.push_back(v); } if (leaves.size() >= 3) { return true; } int start = leaves[0]; vector <int> path = {start, g[start][0]}; while (path.size() < n) { int last = path.back(), prv = path[path.size() - 2]; path.push_back(g[last][0] + g[last][1] - prv); } int numChangesInit = countChanges(path, init); int numChangesTarget = countChanges(path, target); if (numChangesTarget < numChangesInit) { return true; } else if (numChangesTarget > numChangesInit) { return false; } else { return init[start] == target[start]; } } int main() { ios_base::sync_with_stdio(false); int t; cin >> t; while (t--) { int n; cin >> n; string init, target; cin >> init >> target; vector <vector<int>> g(n); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } cout << (solve(n, g, init, target) ? "TAK\n" : "NIE\n"); } return 0; } |