| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1140246 | Persia | Capital City (JOI20_capital_city) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define bit(i, x) (x >> i & 1)
#define ll long long
const int N = 2e5 + 5;
const int mod = 998244353;
using namespace std;
int n, k;
vector<int> c;
vector<vector<int>> G;
int subtask1() {
vector<int> sz(k + 3, 0);
vector<int> cnt(k + 3, 0);
vector<int> vst(n + 3, 0);
vector<int> mark(n + 3, 0);
int res = n;
function<void(int)> dfs = [&](int u) -> void {
vst[u] = 1;
for(int v : G[u]) if(!vst[v] && mark[v]) {
dfs(v);
}
};
for(int i = 1; i <= n; i++) sz[c[i]]++;
for(int mask = 1; mask < (1 << n); mask++) {
cnt.assign(k + 3, 0);
vst.assign(n + 3, 0);
mark.assign(n + 3, 0);
int d = 0, s = 0;
bool flag = 1;
for(int i = 1; i <= n; i++) if(bit(i - 1, mask)) {
d += (cnt[c[i]]++ == 0);
if(s == 0) s = i;
mark[i] = 1;
}
for(int i = 1; i <= n; i++) if(bit(i - 1, mask)) {
if(cnt[c[i]] != sz[c[i]]) {
flag = 0;
break;
}
}
if(flag) {
bool flag2 = 1;
dfs(s);
for(int i = 1; i <= n; i++) if(bit(i - 1, mask)) {
if(!vst[i]) {
flag2 = 0;
break;
}
}
if(flag2) res = min(res, d - 1);
}
}
return res;
}
signed main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
G.assign(n + 3, vector<int>(0));
c.assign(n + 3, 0);
for(int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for(int i = 1; i <= n; i++) {
cin >> c[i];
}
cout << subtask1();
// subtask1();
return 0 ^ 0;
}