Codeforces 701E(DFS)

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

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

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

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}

------ 本文结束 ------