#include <stdio.h> #include <vector> #include <iostream> #include <iostream> const int C=1000001; using namespace std; int s[C], is=0, par[C], ji[C]; int proc_tree(int a, int n, vector <vector <int> > &tab, string ideal){ s[0]=a, is=1; int b; for(int z=1; z<=n; z++) ji[z]=tab[z].size(), par[z]=0; while (is>0){ a=s[is-1]; if (ji[a]>0 && tab[a][ji[a]-1]==par[a]) ji[a]--; if (ji[a]>0) b=s[is]=tab[a][ji[a]-1], par[b]=a, is++, ji[a]--; else is--; } for (int z=2; z<=n; z++){ if (ideal[z] == ideal[par[z]]) return false; } return true; } int times[2]; bool checked[C]; vector <vector <int> > tr(C); int main(){ int n, t, i, a, b, f1, f2, leaf; bool zeros, ones, i_zeros, i_ones, bi_colored; string _cur, _ideal; char start_cur, start_ideal, cur_color, ideal_color; cin >> t; while (t--){ cin >> n; cin >> _cur >> _ideal; _cur = " " + _cur; _ideal = " " + _ideal; for (i=1; i<=n; i++) tr[i].clear(); for (i=0; i<2; i++) times[i]=0; for (i=1; i<=n; i++) checked[i] = false; for (i=1; i<n; i++){ cin >> a >> b; tr[a].push_back(b); tr[b].push_back(a); } if (_cur == _ideal){ printf ("TAK\n"); continue; } zeros=false, ones=false; for (i=0; i<_cur.size(); i++){ if (_cur[i] == '0') zeros = true; if (_cur[i] == '1') ones = true; } i_zeros=false, i_ones=false; for (i=0; i<_ideal.size(); i++){ if (_ideal[i] == '0') i_zeros = true; if (_ideal[i] == '1') i_ones = true; } if (((!zeros) && i_zeros) || ((!ones) && i_ones)){ printf ("NIE\n"); continue; } bi_colored = proc_tree(1, n, tr, _ideal); if (bi_colored){ printf ("NIE\n"); continue; } for (i=1; i<=n; i++){ if (tr[i].size() > 2){ printf ("TAK\n"); break; } if (tr[i].size() == 1) leaf = i; } if (i<=n) continue; a = leaf; checked[a] = true; cur_color = _cur[a]; ideal_color = _ideal[a]; start_cur = cur_color; start_ideal = ideal_color; times[cur_color-48]++; times[ideal_color-48]--; for (i=1; i<n; i++){ b = tr[a][0]; if (checked[b]) b = tr[a][1]; checked[b] = true; if (cur_color != _cur[b]){ cur_color = _cur[b]; times[cur_color-48]++; } if (ideal_color != _ideal[b]){ ideal_color = _ideal[b]; times[ideal_color-48]--; } a = b; } f1 = times[0]; f2 = times[1]; if (f1+f2 >= 1) { printf ("TAK\n"); continue; } if (f1==0 && f2==0 && start_cur==start_ideal){ printf ("TAK\n"); continue; } 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 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 | #include <stdio.h> #include <vector> #include <iostream> #include <iostream> const int C=1000001; using namespace std; int s[C], is=0, par[C], ji[C]; int proc_tree(int a, int n, vector <vector <int> > &tab, string ideal){ s[0]=a, is=1; int b; for(int z=1; z<=n; z++) ji[z]=tab[z].size(), par[z]=0; while (is>0){ a=s[is-1]; if (ji[a]>0 && tab[a][ji[a]-1]==par[a]) ji[a]--; if (ji[a]>0) b=s[is]=tab[a][ji[a]-1], par[b]=a, is++, ji[a]--; else is--; } for (int z=2; z<=n; z++){ if (ideal[z] == ideal[par[z]]) return false; } return true; } int times[2]; bool checked[C]; vector <vector <int> > tr(C); int main(){ int n, t, i, a, b, f1, f2, leaf; bool zeros, ones, i_zeros, i_ones, bi_colored; string _cur, _ideal; char start_cur, start_ideal, cur_color, ideal_color; cin >> t; while (t--){ cin >> n; cin >> _cur >> _ideal; _cur = " " + _cur; _ideal = " " + _ideal; for (i=1; i<=n; i++) tr[i].clear(); for (i=0; i<2; i++) times[i]=0; for (i=1; i<=n; i++) checked[i] = false; for (i=1; i<n; i++){ cin >> a >> b; tr[a].push_back(b); tr[b].push_back(a); } if (_cur == _ideal){ printf ("TAK\n"); continue; } zeros=false, ones=false; for (i=0; i<_cur.size(); i++){ if (_cur[i] == '0') zeros = true; if (_cur[i] == '1') ones = true; } i_zeros=false, i_ones=false; for (i=0; i<_ideal.size(); i++){ if (_ideal[i] == '0') i_zeros = true; if (_ideal[i] == '1') i_ones = true; } if (((!zeros) && i_zeros) || ((!ones) && i_ones)){ printf ("NIE\n"); continue; } bi_colored = proc_tree(1, n, tr, _ideal); if (bi_colored){ printf ("NIE\n"); continue; } for (i=1; i<=n; i++){ if (tr[i].size() > 2){ printf ("TAK\n"); break; } if (tr[i].size() == 1) leaf = i; } if (i<=n) continue; a = leaf; checked[a] = true; cur_color = _cur[a]; ideal_color = _ideal[a]; start_cur = cur_color; start_ideal = ideal_color; times[cur_color-48]++; times[ideal_color-48]--; for (i=1; i<n; i++){ b = tr[a][0]; if (checked[b]) b = tr[a][1]; checked[b] = true; if (cur_color != _cur[b]){ cur_color = _cur[b]; times[cur_color-48]++; } if (ideal_color != _ideal[b]){ ideal_color = _ideal[b]; times[ideal_color-48]--; } a = b; } f1 = times[0]; f2 = times[1]; if (f1+f2 >= 1) { printf ("TAK\n"); continue; } if (f1==0 && f2==0 && start_cur==start_ideal){ printf ("TAK\n"); continue; } printf ("NIE\n"); } return 0;} |