dfs Codeforces Round #364 problem B, Question

Revision en2, by CazadorDivino, 2016-07-26 04:59:17

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;
}

Tags dfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English CazadorDivino 2016-07-26 04:59:17 24
en1 English CazadorDivino 2016-07-26 04:58:02 739 Initial revision (published)