#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
int n, k;
vector<int> ad[N];
int s[N];
int state[N];
int par[N], st[N], ed[N], it;
void dfs(int u, int p = -1) {
st[u] = ++it;
for (const auto& v : ad[u]) {
if (v == p) continue;
par[v] = u;
dfs(v, u);
}
ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
ad[u].push_back(v);
ad[v].push_back(u);
}
for (int i = 1; i <= n; ++i) cin >> s[i];
dfs(1);
auto chk = [&](int group) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1)) continue;
int u = i, v = j;
while (true) {
if ((group >> state[u] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
if (anc(u, v)) break;
u = par[u];
}
while (true) {
if ((group >> state[v] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
if (v == u) break;
v = par[v];
}
}
}
return true;
};
int answer = 1'000'000;
for (int merge = 0; merge < (1 << k); ++merge) {
int root = 0, mask = 0;
for (int i = 1; i <= n; ++i) {
state[i] = s[i];
if (merge >> s[i] - 1 & 1) {
root = (!root ? s[i] : root);
state[i] = root;
}
mask |= (1 << state[i] - 1);
}
bool separable = false;
for (int group = 1; group < mask; ++group) {
bool valid = true;
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1) && state[i] == state[j]) {
valid = false;
}
if (!valid) continue;
separable |= chk(group);
}
if (!separable) answer = min(answer, max(0, __builtin_popcount(merge) - 1));
}
cout << answer << "\n";
}
Compilation message
mergers.cpp: In lambda function:
mergers.cpp:39:28: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
39 | if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1)) continue;
| ~~~~~~~~~^~~
mergers.cpp:39:59: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
39 | if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1)) continue;
| ~~~~~~~~~^~~
mergers.cpp:43:29: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
43 | if ((group >> state[u] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
| ~~~~~~~~~^~~
mergers.cpp:43:60: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
43 | if ((group >> state[u] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
| ~~~~~~~~~^~~
mergers.cpp:48:29: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
48 | if ((group >> state[v] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
| ~~~~~~~~~^~~
mergers.cpp:48:60: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
48 | if ((group >> state[v] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
| ~~~~~~~~~^~~
mergers.cpp: In function 'int32_t main()':
mergers.cpp:62:22: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
62 | if (merge >> s[i] - 1 & 1) {
| ~~~~~^~~
mergers.cpp:66:27: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
66 | mask |= (1 << state[i] - 1);
| ~~~~~~~~~^~~
mergers.cpp:73:29: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
73 | if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1) && state[i] == state[j]) {
| ~~~~~~~~~^~~
mergers.cpp:73:60: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
73 | if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1) && state[i] == state[j]) {
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
