#include <bits/stdc++.h>
#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'
int main() {
#ifdef mlocal
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k; cin >> n >> k;
vector<vi> adj(n);
for_(i, 0, n-1) {
int a, b; cin >> a >> b;
a -= 1; b -= 1;
adj[a].push_back(b); adj[b].push_back(a);
}
vi st(n), ct(n);
for_(i, 0, n) {
cin >> st[i];
st[i] -= 1;
ct[st[i]]++;
}
vector<map<int, int>> mp(n);
vi odd(n);
int ans = 0, oc = 0;
function<void(int,int)> dfs = [&](int p, int parent) {
int badchild = 0;
if (ct[st[p]] != 1) mp[p][st[p]] = 1;
for (auto i: adj[p]) if (i != parent) {
dfs(i, p);
// lone[p] = lone[p] or lone[i];
if (mp[i].size() == 0 or odd[i]) badchild += 1;
if (mp[i].size() > mp[p].size()) swap(mp[p], mp[i]);
vi rem;
for (auto &v: mp[i]) {
mp[p][v.first] += v.second;
if (mp[p][v.first] == ct[v.first]) rem.push_back(v.first);
}
for (auto v: rem) mp[p].erase(v);
}
// cout << p << ": " << mp[p] << endl;
ans += badchild/2;
odd[p] = (badchild%2);
};
int fin = INT_MAX;
// dfs(1, 1);
for_(i, 0, n) {
ans = 0;
odd.assign(n, 0);
mp.assign(n, {});
dfs(i, i);
// if (ans+odd[0] == 0) cout << ".... " << i+1 << endl;
fin = min(fin, ans+odd[i]);
}
cout << fin << endl;
}
Compilation message
mergers.cpp: In function 'int main()':
mergers.cpp:38:15: warning: unused variable 'oc' [-Wunused-variable]
38 | int ans = 0, oc = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
2 ms |
304 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
2 ms |
304 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
2 ms |
304 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3033 ms |
17080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
204 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
204 KB |
Output is correct |
| 11 |
Correct |
2 ms |
304 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
