Untitled
#include<bits/stdc++.h> using namespace std; #define ll long long void solve(){ int n; cin >> n; vector<int> a(n), par(n, -1); vector<int> freq(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; freq[a[i]]++; } vector<vector<int>> g(n); for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } if (n % 2) return void (cout << "-1\n"); for (auto it : freq) if (it % 2 != 0) return void (cout << "-1\n"); vector<int> num_child(n); function<int(int)> build = [&](int node) { int &ret = num_child[node]; ret = 1; for (auto child : g[node]) { if (child != par[node]) { par[child] = node; ret += build(child); } } return ret; }; build(0); vector<int> par_freq(n + 1); function<void(int)> get_ans = [&](int node) { par_freq[a[node]]++; for (auto child : g[node]) { if (child != par[node]) { get_ans(child); } } }; bool ok = false; for (int i = 0; i < n; ++i) { if (num_child[i] == n / 2) { get_ans(i); ok = true; break; } } if (!ok) return void(cout << "-1\n"); int ans = 0; for (int i = 1; i <= n; i++) ans += abs(freq[i] / 2 - par_freq[i]); cout << ans / 2 << "\n"; } int main(){ ios::sync_with_stdio(0), cin.tie(0); int T = 1; cin >> T; while (T--) solve(); }
Leave a Comment