Codeforces 701E(DFS)

Codeforces 701E
题意：有$n$个城市，有$2k$个学校在城市中，要对这$2k$个学校进行连边，使得所有连出来的边的和最大，每条边边权为$1$

考虑每条边对答案的贡献。对于一条边，因为要最大化和，所以他左边的学校一定要连到右边的学校，所以每条边的贡献是$min(left, right)$，$left$是左边的学校个数，$right=2k-left$。DFS 处理即可，随意定一个根都行。

知识点：对于这种路径覆盖，树上计数的题目，多想想边点对答案的贡献。

Codeforces Submission

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
vector<LL> G[200000 + 5];
LL n, k, ai[200000 + 5], ans;
inline void ins(LL x, LL y) {
    G[x].push_back(y), G[y].push_back(x);
}
int dfs(LL u, LL pa) {
    LL siz = ai[u];
    for (LL i = 0; i < (LL)G[u].size(); i++) {
        LL v = G[u][i];
        if (v != pa) {
            LL tmp = dfs(v, u);
            siz += tmp;
            ans += min(tmp, 2ll * k - tmp);
        }
    }
    return siz;
}
void clean() {
    ans = 0, ms(ai, 0);
}
int solve() {
    clean();
    for (LL u, i = 1; i <= 2 * k; i++) scanf("%lld", &u), ai[u] = 1;
    for (LL x, y, i = 1; i < n; i++) scanf("%lld%lld", &x, &y), ins(x, y);
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0; 
}
int main() {
    scanf("%lld%lld", &n, &k), solve();
    return 0;
}