Untitled

 avatar
unknown
c_cpp
a month ago
1.6 kB
1
Indexable
#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