#pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } using Ky = vector <int>; const int maxN = 1 << 19, INF = 1 << 30; char T[maxN], S[maxN]; vector <int> G[maxN]; void dfs(int v, int fat, vector <int>& seq, char* W) { if (W[v] != W[fat]) seq.pb(W[v]); for (int u : G[v]) if (u != fat) dfs(u, v, seq, W); } string path(int n) { vector <int> a, b; int r = 1; while (SZ(G[r]) > 1) r++; dfs(r, 0, a, T); dfs(r, 0, b, S); return SZ(b) < SZ(a) or b == a ? "TAK" : "NIE"; } string nopath(int n, bool zebra) { if (string(T+1) == string(S+1)) return "TAK"; FOR(d, 0, 2) if (count(T+1, T+n+1, '0'+d) == 0 and count(S+1, S+n+1, '0'+d) != 0) return "NIE"; return zebra ? "NIE" : "TAK"; } void solve() { int n, m = 0; scanf ("%d%s%s", &n, T+1, S+1); bool zebra = true; FOR(i, 1, n) { int a, b; scanf ("%d%d", &a, &b); G[a].pb(b); G[b].pb(a); for (int v : {a, b}) remax(m, SZ(G[v])); if (S[a] == S[b]) zebra = false; } printf("%s\n", (m < 3 ? path(n) : nopath(n, zebra)).c_str()); FOR(i, 1, n+1) G[i].resize(0), G[i].shrink_to_fit(); } int main() { int t = 1; scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } 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 | #pragma GCC optimize ("Ofast") #define _USE_MATH_DEFINES #include <bits/stdc++.h> #define FOR(i, a, b) for (auto i=(a); i<(b); i++) #define FORD(i, a, b) for (int i=(a); i>(b); i--) #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define PPC(x) __builtin_popcountll(x) #define MSB(x) (63 - __builtin_clzll(x)) #define LSB(x) __builtin_ctz(x) #define ARG(x, i) (get<i>(x)) #define ithBit(m, i) ((m) >> (i) & 1) #define pb push_back #define ft first #define sd second #define kw(a) ((a) * (a)) #ifdef DEBUG #include "debug.h" #else #define dbg(...) 0 #endif using namespace std; template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b); } template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b); } using Ky = vector <int>; const int maxN = 1 << 19, INF = 1 << 30; char T[maxN], S[maxN]; vector <int> G[maxN]; void dfs(int v, int fat, vector <int>& seq, char* W) { if (W[v] != W[fat]) seq.pb(W[v]); for (int u : G[v]) if (u != fat) dfs(u, v, seq, W); } string path(int n) { vector <int> a, b; int r = 1; while (SZ(G[r]) > 1) r++; dfs(r, 0, a, T); dfs(r, 0, b, S); return SZ(b) < SZ(a) or b == a ? "TAK" : "NIE"; } string nopath(int n, bool zebra) { if (string(T+1) == string(S+1)) return "TAK"; FOR(d, 0, 2) if (count(T+1, T+n+1, '0'+d) == 0 and count(S+1, S+n+1, '0'+d) != 0) return "NIE"; return zebra ? "NIE" : "TAK"; } void solve() { int n, m = 0; scanf ("%d%s%s", &n, T+1, S+1); bool zebra = true; FOR(i, 1, n) { int a, b; scanf ("%d%d", &a, &b); G[a].pb(b); G[b].pb(a); for (int v : {a, b}) remax(m, SZ(G[v])); if (S[a] == S[b]) zebra = false; } printf("%s\n", (m < 3 ? path(n) : nopath(n, zebra)).c_str()); FOR(i, 1, n+1) G[i].resize(0), G[i].shrink_to_fit(); } int main() { int t = 1; scanf ("%d", &t); FOR(tid, 1, t+1) { //printf("Case #%d: ", tid); solve(); } return 0; } |