Блог пользователя CazadorDivino

Автор CazadorDivino, история, 8 лет назад, По-английски

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

Теги dfs
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 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)