#include <bits/stdc++.h> using namespace std; int dfs(const int& v, const int& p, const string& s, const vector<vector<int>>& adj) { int cnt = 0; for (auto& x : adj[v]) { if (x == p) continue; cnt += (s[v] != s[x]) + dfs(x, v, s, adj); } return cnt; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; string b1, b2; cin >> b1 >> b2; vector<vector<int>> adj(n); for (int i = 1; i < n; ++i) { int a, b; cin >> a >> b; adj[--a].push_back(--b); adj[b].push_back(a); } cout << (dfs(0, 0, b1, adj) > dfs(0, 0, b2, adj) or b1 == b2 ? "TAK" : "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 | #include <bits/stdc++.h> using namespace std; int dfs(const int& v, const int& p, const string& s, const vector<vector<int>>& adj) { int cnt = 0; for (auto& x : adj[v]) { if (x == p) continue; cnt += (s[v] != s[x]) + dfs(x, v, s, adj); } return cnt; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; string b1, b2; cin >> b1 >> b2; vector<vector<int>> adj(n); for (int i = 1; i < n; ++i) { int a, b; cin >> a >> b; adj[--a].push_back(--b); adj[b].push_back(a); } cout << (dfs(0, 0, b1, adj) > dfs(0, 0, b2, adj) or b1 == b2 ? "TAK" : "NIE") << '\n'; } } |