#include <bits/stdc++.h> #define int long long using namespace std; string res_sign[2]; void calc_sign(int parent, int head, const string &input, const vector<vector<int>> &nei, bool num) { for (int i = 0; i < nei[head].size(); i++) { int neighbour = nei[head][i]; // cerr << "parent: " << parent << endl; // cerr << "head: " << head << endl; // cerr << "neighbour: " << neighbour << endl; if (neighbour != parent) { if (input[neighbour] != input[head]) { res_sign[num] += input[neighbour]; } calc_sign(head, neighbour, input, nei, num); } } } signed main() { int t; cin >> t; while (t--) { int n; string s_beg, s_end; res_sign[0].clear(); res_sign[1].clear(); cin >> n >> s_beg >> s_end; // cerr << "n: " << n << endl; vector<vector<int>> nei(n); for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; nei[x - 1].push_back(y - 1); nei[y - 1].push_back(x - 1); } int cnt_1_beg = 0; int cnt_1_end = 0; for (int i = 0; i < n; i++) { if (s_beg[i] == '1') { cnt_1_beg++; } if (s_end[i] == '1') { cnt_1_end++; } } if (cnt_1_beg == n && cnt_1_end == n) { cout << "TAK" << endl; } else if (cnt_1_beg == 0 && cnt_1_end == 0) { cout << "TAK" << endl; } else if (cnt_1_beg == n && cnt_1_end < n) { cout << "NIE" << endl; } else if (cnt_1_beg == 0 && cnt_1_end > 0) { cout << "NIE" << endl; } else { bool has_3 = false; int head = -1; for (int i = 0; i < nei.size(); i++) { if (nei[i].size() > 2) { has_3 = true; } if (nei[i].size() == 1) { head = i; } } if (has_3) { cout << "TAK" << endl; } else { res_sign[0] += s_beg[head]; res_sign[1] += s_end[head]; calc_sign(head, head, s_beg, nei, 0); calc_sign(head, head, s_end, nei, 1); if (res_sign[0].size() > res_sign[1].size()) { cout << "TAK" << endl; } else if (res_sign[0].size() < res_sign[1].size()) { cout << "NIE" << endl; } else { if (res_sign[0] == res_sign[1]) { cout << "TAK" << endl; } else { cout << "NIE" << endl; } } } } } }
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 | #include <bits/stdc++.h> #define int long long using namespace std; string res_sign[2]; void calc_sign(int parent, int head, const string &input, const vector<vector<int>> &nei, bool num) { for (int i = 0; i < nei[head].size(); i++) { int neighbour = nei[head][i]; // cerr << "parent: " << parent << endl; // cerr << "head: " << head << endl; // cerr << "neighbour: " << neighbour << endl; if (neighbour != parent) { if (input[neighbour] != input[head]) { res_sign[num] += input[neighbour]; } calc_sign(head, neighbour, input, nei, num); } } } signed main() { int t; cin >> t; while (t--) { int n; string s_beg, s_end; res_sign[0].clear(); res_sign[1].clear(); cin >> n >> s_beg >> s_end; // cerr << "n: " << n << endl; vector<vector<int>> nei(n); for (int i = 0; i < n - 1; i++) { int x, y; cin >> x >> y; nei[x - 1].push_back(y - 1); nei[y - 1].push_back(x - 1); } int cnt_1_beg = 0; int cnt_1_end = 0; for (int i = 0; i < n; i++) { if (s_beg[i] == '1') { cnt_1_beg++; } if (s_end[i] == '1') { cnt_1_end++; } } if (cnt_1_beg == n && cnt_1_end == n) { cout << "TAK" << endl; } else if (cnt_1_beg == 0 && cnt_1_end == 0) { cout << "TAK" << endl; } else if (cnt_1_beg == n && cnt_1_end < n) { cout << "NIE" << endl; } else if (cnt_1_beg == 0 && cnt_1_end > 0) { cout << "NIE" << endl; } else { bool has_3 = false; int head = -1; for (int i = 0; i < nei.size(); i++) { if (nei[i].size() > 2) { has_3 = true; } if (nei[i].size() == 1) { head = i; } } if (has_3) { cout << "TAK" << endl; } else { res_sign[0] += s_beg[head]; res_sign[1] += s_end[head]; calc_sign(head, head, s_beg, nei, 0); calc_sign(head, head, s_end, nei, 1); if (res_sign[0].size() > res_sign[1].size()) { cout << "TAK" << endl; } else if (res_sign[0].size() < res_sign[1].size()) { cout << "NIE" << endl; } else { if (res_sign[0] == res_sign[1]) { cout << "TAK" << endl; } else { cout << "NIE" << endl; } } } } } } |