#include"bits/stdc++.h"
#define int long long
#define endl '\n'
#define USACO(x) ifstream cin ((string)#x + ".in"); ofstream cout((string)#x + ".out")
using namespace std;
int n, k;
vector<int> adj[500001];
int s[500001];
int tot[500001];
int subtree[500001];
map<int,int>* s2b[500001];
int cnt[500001];
bool bad[500001];
void inc (int a, int b, int v) {
(*s2b[a])[b] += v;
if ((*s2b[a])[b] == tot[b]) cnt[a]++;
}
int ans = INT_MAX;
void dfs (int cur, int par) {
// cerr << cur << " " << par << endl;
subtree[cur] = 1;
if (adj[cur].size() == 1 and cur != 1) {
s2b[cur] = new map<int,int>();
inc(cur, s[cur], 1);
ans = min(ans, (int)abs(cnt[cur] - (int)((*s2b[cur]).size())));
bad[cur] = (cnt[cur] == (int)((*s2b[cur]).size()));
return;
}
int best = -1;
for (int i : adj[cur]) {
if (i != par) {
dfs(i, cur);
subtree[cur] += subtree[i];
if (best == -1 or subtree[i] > subtree[best]) best = i;
}
}
s2b[cur] = s2b[best];
cnt[cur] = cnt[best];
for (int i : adj[cur]) {
if (i != par and i != best) {
for (auto j : (*s2b[i])) {
inc(cur, j.first, j.second);
}
*s2b[i].clear();
}
}
inc(cur, s[cur], 1);
ans = min(ans, (int)abs(cnt[cur] - (int)((*s2b[cur]).size())));
bad[cur] = (cnt[cur] == (int)((*s2b[cur]).size()));
}
int calc_ans (int cur, int par) {
int ret = 0;
for (int i : adj[cur]) {
if (i != par) {
ret += calc_ans(i, cur);
}
}
if (ret == 0 and cur != 1) ret += bad[cur];
return ret;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1 ; i < n ; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1 ; i <= n ; i++) {
cin >> s[i];
tot[s[i]]++;
}
dfs(1, 0);
cout << ceil(calc_ans(1, 0) / 2.0);
}
Compilation message
mergers.cpp: In function 'void dfs(long long int, long long int)':
mergers.cpp:51:21: error: request for member 'clear' in 's2b[i]', which is of pointer type 'std::map<long long int, long long int>*' (maybe you meant to use '->' ?)
51 | *s2b[i].clear();
| ^~~~~
