Untitled
unknown
c_cpp
5 months ago
1.2 kB
7
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long int tt, tc; void solve() { int n; cin >> n; vector<int> col(n); for (int& u : col) { cin >> u; --u; } vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } vector<int> d(n), p(n, -1); vector<int> bfs = {0}; for (int i = 0; i < n; i++) { int v = bfs[i]; for (int u : g[v]) if (u != p[v]) { p[u] = v; d[u] = d[v] + 1; bfs.push_back(u); } } vector<vector<int>> of_color(n); for (int i = 0; i < n; i++) { of_color[col[i]].push_back(d[i] & 1); } for (int c = 0; c < n; c++) { auto& V = of_color[c]; if (V.empty()) continue; for (int i = 1; i < (int)V.size(); i++) if (V[i] != V[i - 1]) { cout << -1 << "\n"; return; } } int occ = 0; for (int u : d) occ += (u & 1); cout << min(occ, n - occ) << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); tt = 1, tc = 1; // cin >> tt; while (tt--) { solve(); tc++; } }
Editor is loading...
Leave a Comment