#include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 100100; int n; char sta[N], fin[N], lsta[N], lfin[N]; vector<int> g[N]; bool solve_line() { int s = -1; FOR(i,n) if (SZ(g[i]) == 1) s = i; int prv = -1; FOR(i,n) { lsta[i] = sta[s]; lfin[i] = fin[s]; FOR(j,SZ(g[s])) if (g[s][j] != prv) { prv = s; s = g[s][j]; break; } } int sw_sta = 0, sw_fin = 0; FOR(i,n-1) { if (lsta[i] != lsta[i+1]) sw_sta++; if (lfin[i] != lfin[i+1]) sw_fin++; } if (sw_sta > sw_fin) return true; if (sw_sta < sw_fin) return false; return lsta[0] == lfin[0]; } bool test() { scanf("%d %s %s", &n, sta, fin); FOR(i,n) g[i].clear(); FOR(i,n-1) { int a,b; scanf("%d%d", &a, &b); a--; b--; g[a].pb(b); g[b].pb(a); } bool same = true; int mask_sta = 0, mask_fin = 0; FOR(i,n) { if (sta[i] != fin[i]) same = false; if (sta[i] == '0') mask_sta |= 1; if (sta[i] == '1') mask_sta |= 2; if (fin[i] == '0') mask_fin |= 1; if (fin[i] == '1') mask_fin |= 2; } //cerr << same << " " << mask_sta << " " << mask_fin << "\n"; if (same) return true; if (mask_sta != 3) return false; if (mask_fin != 3) return true; int cnt1 = 0; FOR(i,n) if (SZ(g[i]) == 1) cnt1++; //cerr << "cnt1 = " << cnt1 << "\n"; /// line if (cnt1 == 2) return solve_line(); FOR(i,n) FOR(j,SZ(g[i])) if (fin[i] == fin[g[i][j]]) return true; return false; } int main() { int tt; scanf("%d", &tt); FOR(ii,tt) { if (test()) printf("TAK\n"); else printf("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 | #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for (int i = (a); i <= (b); ++i) #define REPD(i,a,b) for (int i = (a); i >= (b); --i) #define FORI(i,n) REP(i,1,n) #define FOR(i,n) REP(i,0,int(n)-1) #define mp make_pair #define pb push_back #define pii pair<int,int> #define vi vector<int> #define ll long long #define SZ(x) int((x).size()) #define DBG(v) cerr << #v << " = " << (v) << endl; #define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++) #define fi first #define se second const int N = 100100; int n; char sta[N], fin[N], lsta[N], lfin[N]; vector<int> g[N]; bool solve_line() { int s = -1; FOR(i,n) if (SZ(g[i]) == 1) s = i; int prv = -1; FOR(i,n) { lsta[i] = sta[s]; lfin[i] = fin[s]; FOR(j,SZ(g[s])) if (g[s][j] != prv) { prv = s; s = g[s][j]; break; } } int sw_sta = 0, sw_fin = 0; FOR(i,n-1) { if (lsta[i] != lsta[i+1]) sw_sta++; if (lfin[i] != lfin[i+1]) sw_fin++; } if (sw_sta > sw_fin) return true; if (sw_sta < sw_fin) return false; return lsta[0] == lfin[0]; } bool test() { scanf("%d %s %s", &n, sta, fin); FOR(i,n) g[i].clear(); FOR(i,n-1) { int a,b; scanf("%d%d", &a, &b); a--; b--; g[a].pb(b); g[b].pb(a); } bool same = true; int mask_sta = 0, mask_fin = 0; FOR(i,n) { if (sta[i] != fin[i]) same = false; if (sta[i] == '0') mask_sta |= 1; if (sta[i] == '1') mask_sta |= 2; if (fin[i] == '0') mask_fin |= 1; if (fin[i] == '1') mask_fin |= 2; } //cerr << same << " " << mask_sta << " " << mask_fin << "\n"; if (same) return true; if (mask_sta != 3) return false; if (mask_fin != 3) return true; int cnt1 = 0; FOR(i,n) if (SZ(g[i]) == 1) cnt1++; //cerr << "cnt1 = " << cnt1 << "\n"; /// line if (cnt1 == 2) return solve_line(); FOR(i,n) FOR(j,SZ(g[i])) if (fin[i] == fin[g[i][j]]) return true; return false; } int main() { int tt; scanf("%d", &tt); FOR(ii,tt) { if (test()) printf("TAK\n"); else printf("NIE\n"); } return 0; } |