#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;
typedef long long ll;
const int N = 3000 + 7;
vector <int> g[N];
int c[N];
bool bad[N][N];
int par[N], cnt[N];
int get(int a) {
return (a == par[a] ? a : par[a] = get(par[a]));
}
void join(int a, int b) {
a = get(a);
b = get(b);
if (a != b) {
par[a] = b;
cnt[b] += cnt[a];
++cnt[b];
}
}
vector <int> path;
void dfs(int u, int p = -1) {
path.push_back(u);
if (c[path.back()] == c[path.front()]) {
for (int v : path) {
if (c[v] != c[u]) {
bad[c[u]][c[v]] = 1;
}
}
}
for (auto v : g[u]) {
if (v != p) {
dfs(v, u);
}
}
path.pop_back();
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
int n, k;
cin >> n >> k;
for (int i = 0; i + 1 < n; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i < n; ++i) {
cin >> c[i];
--c[i];
}
for (int i = 0; i < n; ++i) {
dfs(i, -1);
}
for (int i = 0; i < k; ++i) {
par[i] = i;
}
for (int i = 0; i < k; ++i) {
for (int j = i + 1; j < k; ++j) {
if (bad[i][j] && bad[j][i]) {
join(i, j);
}
}
}
vector <int> ok(k, true);
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) {
if (bad[i][j] && get(i) != get(j)) {
ok[get(i)] = false;
}
}
}
int ans = n;
bool fnd = false;
for (int i = 0; i < k; ++i) {
if (ok[get(i)]) {
ans = min(ans, cnt[get(i)]);
fnd = true;
}
}
assert(fnd);
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Runtime error |
72 ms |
2296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
4 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Runtime error |
72 ms |
2296 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |