#include<bits/stdc++.h> #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define pll pair<ll, ll> #define vii vector<pii> #define vb vector<bool> #define vvb vector<vb> #define vl vector<ll> #define endl '\n' #define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pb push_back #define ll long long #define f first #define s second using namespace std; vvi v; string s1, s2; int n; bool spychacz(int e, int p, bool spych) { vi t(2, 0); for(auto it : v[e]) if(it != p) t[s2[it-1]-'0']++; if((spych and t[1]) or (!spych and t[0])) return true; for(auto it : v[e]) if(it != p) return spychacz(it, e, !spych); return false; } pii napierdalaj_dp(int e, int p, int ile1 = 0, int ile2 = 0) { if(s1[e-1] != s1[p-1]) ile1++; if(s2[e-1] != s2[p-1]) ile2++; for(auto it : v[e]) if(it != p) return napierdalaj_dp(it, e, ile1, ile2); return {ile1, ile2}; } bool go_dp() { for(int e = 1; e <= n; e++) if(v[e].size() <= 1) { auto it = napierdalaj_dp(e, e); if(it.f == it.s) return s1[e-1] == s2[e-1]; return it.f > it.s; } return false; } int main() { turbo int q; cin >> q; while(q--) { cin >> n >> s1 >> s2; v = vvi(n+10); vi t1(2, 0), t2(2, 0); for(auto it : s1) t1[it-'0']++; for(auto it : s2) t2[it-'0']++; for(int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); } if((!t1[0] and t2[0]) or (!t1[1] and t2[1])) { cout << "NIE\n"; continue; } if(s1 == s2) { cout << "TAK\n"; continue; } int ile_ancymonkow = 0; bool senko = false; for(int e = 1; e <= n; e++) if(v[e].size() >= 3) { ile_ancymonkow++; int murzyn = 0; for(auto it : v[e]) if(s2[it-1] == '1') murzyn++; if(murzyn != v[e].size() and murzyn) { senko = true; break; } if((murzyn == v[e].size() and s2[e-1] == '1') or (!murzyn and s2[e-1] == '0')) { senko = true; break; } } if(senko) { cout << "TAK\n"; continue; } if(!ile_ancymonkow) { cout << (go_dp() ? "TAK\n" : "NIE\n"); continue; } for(int e = 1; e <= n; e++) if(v[e].size() >= 3) for(auto it : v[e]) if(spychacz(it, e, !(s2[e-1]-'0'))) senko = true; cout << (senko ? "TAK\n" : "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 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 129 130 131 | #include<bits/stdc++.h> #define vi vector<int> #define vvi vector<vi> #define pii pair<int, int> #define pll pair<ll, ll> #define vii vector<pii> #define vb vector<bool> #define vvb vector<vb> #define vl vector<ll> #define endl '\n' #define turbo ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define pb push_back #define ll long long #define f first #define s second using namespace std; vvi v; string s1, s2; int n; bool spychacz(int e, int p, bool spych) { vi t(2, 0); for(auto it : v[e]) if(it != p) t[s2[it-1]-'0']++; if((spych and t[1]) or (!spych and t[0])) return true; for(auto it : v[e]) if(it != p) return spychacz(it, e, !spych); return false; } pii napierdalaj_dp(int e, int p, int ile1 = 0, int ile2 = 0) { if(s1[e-1] != s1[p-1]) ile1++; if(s2[e-1] != s2[p-1]) ile2++; for(auto it : v[e]) if(it != p) return napierdalaj_dp(it, e, ile1, ile2); return {ile1, ile2}; } bool go_dp() { for(int e = 1; e <= n; e++) if(v[e].size() <= 1) { auto it = napierdalaj_dp(e, e); if(it.f == it.s) return s1[e-1] == s2[e-1]; return it.f > it.s; } return false; } int main() { turbo int q; cin >> q; while(q--) { cin >> n >> s1 >> s2; v = vvi(n+10); vi t1(2, 0), t2(2, 0); for(auto it : s1) t1[it-'0']++; for(auto it : s2) t2[it-'0']++; for(int i = 0; i < n-1; i++) { int a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); } if((!t1[0] and t2[0]) or (!t1[1] and t2[1])) { cout << "NIE\n"; continue; } if(s1 == s2) { cout << "TAK\n"; continue; } int ile_ancymonkow = 0; bool senko = false; for(int e = 1; e <= n; e++) if(v[e].size() >= 3) { ile_ancymonkow++; int murzyn = 0; for(auto it : v[e]) if(s2[it-1] == '1') murzyn++; if(murzyn != v[e].size() and murzyn) { senko = true; break; } if((murzyn == v[e].size() and s2[e-1] == '1') or (!murzyn and s2[e-1] == '0')) { senko = true; break; } } if(senko) { cout << "TAK\n"; continue; } if(!ile_ancymonkow) { cout << (go_dp() ? "TAK\n" : "NIE\n"); continue; } for(int e = 1; e <= n; e++) if(v[e].size() >= 3) for(auto it : v[e]) if(spychacz(it, e, !(s2[e-1]-'0'))) senko = true; cout << (senko ? "TAK\n" : "NIE\n"); } } |