#include <cassert> #include <iostream> #include <stack> #include <string.h> #include <vector> using namespace std; #define N 100000 char A[N]; char B[N]; vector<int> G[N]; int n; bool is_leaf(int v) { return G[v].size() == 1; } bool solve() { bool all_eq = true; bool containa[2] = {false, false}; bool containb[2] = {false, false}; bool branch = false; int leaf = -1; for (int i = 0; i < n; i++) { all_eq = all_eq && A[i] == B[i]; if (A[i] == '0') containa[0] = true; else containa[1] = true; if (B[i] == '0') containb[0] = true; else containb[1] = true; branch = branch || G[i].size() >= 3; if (leaf == -1 && is_leaf(i)) leaf = i; } if (all_eq) { return true; } for (int i = 0; i < 2; i++) { if (containa[i] && !containb[1 - i]) { return true; } if (containb[i] && !containa[i]) return false; } // cout << "dupa" << endl; assert(containa[0] && containa[1]); if (branch) return true; // cout << "dupa1" << endl; assert(leaf != -1); // cout << "dupa1" << endl; int prev = leaf, cur = G[leaf][0], tmp; int inca = 0, incb = 0, deca = 0, decb = 0; while (true) { if (A[cur] != A[prev]) { if (A[cur] == '0') deca += 1; else inca += 1; } if (B[cur] != B[prev]) { if (B[cur] == '0') decb += 1; else incb += 1; } if (is_leaf(cur)) break; tmp = cur; cur = G[cur][0] != prev ? G[cur][0] : G[cur][1]; prev = tmp; } // cout << inca << endl; // cout << incb << endl; // cout << deca << endl; // cout << decb << endl; return ( inca > incb && deca >= decb ) || ( inca >= incb && deca > decb ) || ( inca == incb && deca == decb && A[leaf] == B[leaf]); } int main() { ios_base::sync_with_stdio(0); int t, w, v; cin >> t; for (int i = 0; i < t; i++) { cin >> n; for (int j = 0; j < n; j++) { cin >> A[j]; } for (int j = 0; j < n; j++) { cin >> B[j]; } for (int j = 0; j < n; j++) { G[j].clear(); G[j].reserve(N); } for (int j = 0; j < n - 1; j++) { cin >> w >> v; w -= 1; v -= 1; G[w].push_back(v); G[v].push_back(w); } // if (i == 81) { // cout << n << endl; // for (int i = 0; i < n; i++) { // cout << A[i]; // } // cout << endl; // for (int i = 0; i < n; i++) { // cout << B[i]; // } // cout << endl; // cout << (solve() ? "TAK" : "NIE") << endl; // } cout << (solve() ? "TAK" : "NIE") << endl; } 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 <cassert> #include <iostream> #include <stack> #include <string.h> #include <vector> using namespace std; #define N 100000 char A[N]; char B[N]; vector<int> G[N]; int n; bool is_leaf(int v) { return G[v].size() == 1; } bool solve() { bool all_eq = true; bool containa[2] = {false, false}; bool containb[2] = {false, false}; bool branch = false; int leaf = -1; for (int i = 0; i < n; i++) { all_eq = all_eq && A[i] == B[i]; if (A[i] == '0') containa[0] = true; else containa[1] = true; if (B[i] == '0') containb[0] = true; else containb[1] = true; branch = branch || G[i].size() >= 3; if (leaf == -1 && is_leaf(i)) leaf = i; } if (all_eq) { return true; } for (int i = 0; i < 2; i++) { if (containa[i] && !containb[1 - i]) { return true; } if (containb[i] && !containa[i]) return false; } // cout << "dupa" << endl; assert(containa[0] && containa[1]); if (branch) return true; // cout << "dupa1" << endl; assert(leaf != -1); // cout << "dupa1" << endl; int prev = leaf, cur = G[leaf][0], tmp; int inca = 0, incb = 0, deca = 0, decb = 0; while (true) { if (A[cur] != A[prev]) { if (A[cur] == '0') deca += 1; else inca += 1; } if (B[cur] != B[prev]) { if (B[cur] == '0') decb += 1; else incb += 1; } if (is_leaf(cur)) break; tmp = cur; cur = G[cur][0] != prev ? G[cur][0] : G[cur][1]; prev = tmp; } // cout << inca << endl; // cout << incb << endl; // cout << deca << endl; // cout << decb << endl; return ( inca > incb && deca >= decb ) || ( inca >= incb && deca > decb ) || ( inca == incb && deca == decb && A[leaf] == B[leaf]); } int main() { ios_base::sync_with_stdio(0); int t, w, v; cin >> t; for (int i = 0; i < t; i++) { cin >> n; for (int j = 0; j < n; j++) { cin >> A[j]; } for (int j = 0; j < n; j++) { cin >> B[j]; } for (int j = 0; j < n; j++) { G[j].clear(); G[j].reserve(N); } for (int j = 0; j < n - 1; j++) { cin >> w >> v; w -= 1; v -= 1; G[w].push_back(v); G[v].push_back(w); } // if (i == 81) { // cout << n << endl; // for (int i = 0; i < n; i++) { // cout << A[i]; // } // cout << endl; // for (int i = 0; i < n; i++) { // cout << B[i]; // } // cout << endl; // cout << (solve() ? "TAK" : "NIE") << endl; // } cout << (solve() ? "TAK" : "NIE") << endl; } return 0; } |