CazadorDivino's blog

By CazadorDivino, history, 8 years ago, In English

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
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)