#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ST first #define ND second #define SIZE(a) ((int)a.size()) bool solve() { int n; cin >> n; string start, end; cin >> start >> end; int ones=0, zeros=0; for(char c : start) { if(c == '1') { ones++; } else { zeros++; } } vector<int> deg(n); bool one_color_edge = false; int max_deg = 0; vector<vector<int>> v(n); for(int i=0; i < n-1; i++) { int a, b; cin >> a >> b; a--; b--; deg[a]++; deg[b]++; max_deg = max(max_deg, max(deg[a], deg[b])); if(end[a] == end[b]) { one_color_edge = true; } v[a].push_back(b); v[b].push_back(a); } if(ones == 0 || zeros == 0) { return start == end; } else if(max_deg <= 2) { int a=0; while(deg[a] > 1) { a++; } int prev = -1; string start_cc, end_cc; start_cc = start[a], end_cc = end[a]; do{ for(int b : v[a]) { if(b != prev) { prev = a; a = b; break; } } if(start_cc.back() != start[a]) { start_cc+= start[a]; } if(end_cc.back() != end[a]) { end_cc+= end[a]; } }while(deg[a] > 1); // cerr << start_cc << " " << end_cc << "\n"; return (start_cc.size() > end_cc.size() || (start_cc.size() == end_cc.size() && start_cc[0] == end_cc[0])); } else if(one_color_edge) { return true; } else { return start == end; } } int main() { ios_base::sync_with_stdio(0); int t; cin >> t; while(t--) { if(solve()) { cout << "TAK\n"; } else { cout << "NIE\n"; } } }
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 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ST first #define ND second #define SIZE(a) ((int)a.size()) bool solve() { int n; cin >> n; string start, end; cin >> start >> end; int ones=0, zeros=0; for(char c : start) { if(c == '1') { ones++; } else { zeros++; } } vector<int> deg(n); bool one_color_edge = false; int max_deg = 0; vector<vector<int>> v(n); for(int i=0; i < n-1; i++) { int a, b; cin >> a >> b; a--; b--; deg[a]++; deg[b]++; max_deg = max(max_deg, max(deg[a], deg[b])); if(end[a] == end[b]) { one_color_edge = true; } v[a].push_back(b); v[b].push_back(a); } if(ones == 0 || zeros == 0) { return start == end; } else if(max_deg <= 2) { int a=0; while(deg[a] > 1) { a++; } int prev = -1; string start_cc, end_cc; start_cc = start[a], end_cc = end[a]; do{ for(int b : v[a]) { if(b != prev) { prev = a; a = b; break; } } if(start_cc.back() != start[a]) { start_cc+= start[a]; } if(end_cc.back() != end[a]) { end_cc+= end[a]; } }while(deg[a] > 1); // cerr << start_cc << " " << end_cc << "\n"; return (start_cc.size() > end_cc.size() || (start_cc.size() == end_cc.size() && start_cc[0] == end_cc[0])); } else if(one_color_edge) { return true; } else { return start == end; } } int main() { ios_base::sync_with_stdio(0); int t; cin >> t; while(t--) { if(solve()) { cout << "TAK\n"; } else { cout << "NIE\n"; } } } |