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
#include <bits/stdc++.h>

void DFS(std::vector<int> *, int, int, bool *, std::string, std::string, int &, int &);

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int q;
    std::cin >> q;
    while (q > 0) {
        size_t n;
        std::cin >> n;
        
        std::vector<int> *G = new std::vector<int> [n + 1];
        std::string A;
        std::string B;
        std::cin >> A >> B;

        for (int i = 0; i < n - 1; ++i) {
            int a, b;
            std::cin >> a >> b;
            G[a].push_back(b);
            G[b].push_back(a);
        }

        bool is_r_s = false;
        bool is_b_s = false;
        bool is_r_e = false;
        bool is_b_e = false;

        for (int i = 0; i < n; ++i) {
            (A[i] == 1) ? is_r_s = true : is_b_s = true;
            (B[i] == 1) ? is_r_e = true : is_b_e = true;
        }

        bool is_3_in_G = false;
        int node_1 = -1;
        for (int i = 1; i <= n; ++i) {
            if (G[i].size() == 1) node_1 = i;
            if (G[i].size() == 3) is_3_in_G = true;
        }

        if (is_3_in_G) {
            if (is_r_e && !is_r_s) std::cout << "NIE\n";
            else if (is_b_e && !is_b_s) std::cout << "NIE\n";
            else std::cout << "TAK\n";
        }
        else {
            char node_A = A[node_1 - 1];
            char node_B = B[node_1 - 1];

            bool *vis = new bool [n + 1];
            for (int i = 0; i <= n + 1; ++i)
                vis[i] = false;
            vis[node_1] = true;
            int licznik_A = (node_A == node_B) ? 1 : 0;
            int licznik_B = 1;
            DFS(G, node_1, node_1, vis, A, B, licznik_A, licznik_B);
            (licznik_B > licznik_A) ? std::cout << "NIE\n" : std::cout << "TAK\n";
        }

        delete [] G;
        --q;
    }
    return 0;
}

void DFS(std::vector<int> *G, int it, int past_it, bool *vis, std::string A, std::string B, int &licz_A, int &licz_B) {
    if (it == past_it) DFS(G, G[it][0], past_it, vis, A, B, licz_A, licz_B);
    else {
        for (int i = 0; i < G[it].size(); ++i)
            if (!vis[G[it][i]]) {
                if (A[it] != A[G[it][i]]) ++licz_A;
                if (B[it] != B[G[it][i]]) ++licz_B;
                vis[G[it][i]] = true;
                DFS(G, G[it][0], it, vis, A, B, licz_A, licz_B);
            }
    }
    return;
}