I understand the code, but why min(cc[u], k + k — cc[u]), this is magic for me. Anyone can help me. Thanks.
inline void dfs(int u, int p) {
cout<< "dfs("<< u<<","<<p<<")"<<endl;
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != p) {
dfs(v, u);
cc[u] += cc[v];
}
}
ans += min(cc[u], k + k - cc[u]);
}
int main() {
cin >> n >> k;
rep (i, 0, k + k) {
int u;
cin >> u;
cc[u]++;
}
rep (i, 1, n) {
int u, v;
cin >> u >> v;
adj[u].PB(v);
adj[v].PB(u);
}
dfs(1, 0);
cout << ans << endl;
return 0;
}
In the subtree of v at most
min(cc[u], k + k - cc[u])
can use the edge from par(v) to v for being pair.(being pair with out of subtree of v)