[AGC034E] Complete Compress

题解

感觉比 E 题难但是过的人远比 E 题多...

不知道 piece 怎么翻译,后面用石子代指 piece。

先枚举一个点 \(r\),然后考虑把所有石子都移动到点 \(r\) 上的情况。把 \(r\) 作为根,考虑每个石子到 \(r\) 的距离之和 \(s\),显然操作不会改变 \(s\) 的奇偶性,所以如果 \(s\) 是偶数,不存在把所有石子移动到 \(r\) 的方案。如果存在把所有石子移动到 \(r\) 的方案,那么最少步数必然是 \(\frac s 2\),因为如果一个方案中有一次使一个石子到根的距离变小,另一个石子到根的距离变大,一定可以调整为一个步数更少的的方案。接下来我们只需考虑如何检验方案是否存在,如果我们只考虑一个子树内的操作,不难发现最优方案一定可以调整为一种先进行完全在某个儿子的子树内部的操作,再进行两个石子在不同儿子子树内部的操作的方案。所以我们可以做树形 dp,设 \(f_{ij}\) 表示是否可以对 \(i\) 的子树内部的石子进行操作,使得 \(i\) 子树内部石子到根的距离之和为 \(j\)。考虑怎么转移,假设我们已经决定了点 \(u\) 每个儿子子树内的操作,经过这些操作时候第 \(i\) 个儿子子树内的石子到 \(u\) 距离之和为 \(s_i\),共有 \(c\) 个儿子,设 \(\max s_i = t\),可以证明,\(f_{uj} = 1\),当且仅当 \(j\)\(\sum s_i\) 奇偶性相同,且 \(j \ge 2t - \sum s_i\)。这样的复杂度太大了,不难归纳证明对于任意的 \(i\)\(f_{ij} = 1\)\(j\) 必然是某个区间内的所有奇数 / 偶数。利用这个性质,我们 dp 使只需要记一个区间即可。在计算这个区间的右边界时,只需把所有儿子的子树中的石子到这个儿子的距离之和都取到最大即可。在计算左边界时,枚举取到左边界的方案中哪个儿子的 \(s_i\) 最大,让其他儿子的 \(s_i\) 都尽量小,这个儿子的 \(s_i\) 在大于等于其他儿子的前提下尽量小,更新一下左边界即可。具体实现可以看代码。

代码

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>

using namespace std;

const int maxn = 2010;
const int inf = 0x3f3f3f3f;

int ans = inf;

int n, l[maxn], sz[maxn], lb[maxn], rb[maxn], dep[maxn], e;
char S[maxn];

struct Edge {
int v, x;
} E[maxn << 1];

int Max(int u, int v) {
if ((u ^ v) & 1) ++ v;
return max(u, v);
}

void dfs(int u, int fa) {
sz[u] = (S[u] == '1'); lb[u] = inf; rb[u] = 0;
int sum = 0, mx = 0, cmx = 0;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != fa) {
dep[v] = dep[u] + 1;
dfs(v, u);
sz[u] += sz[v];
rb[u] += sz[v] + rb[v];
sum += sz[v] + lb[v];
if (sz[v] + lb[v] >= mx) {
cmx = mx;
mx = sz[v] + lb[v];
} else if (sz[v] + lb[v] > cmx) {
cmx = sz[v] + lb[v];
}
}
}
lb[u] = sum;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (v != fa) {
int t = mx;
if (sz[v] + lb[v] == mx) t = cmx;
int w = Max(sz[v] + lb[v], t);
if (w > sz[v] + rb[v]) continue;
int s = sum - sz[v] - lb[v] + w;
lb[u] = min(lb[u], max(s & 1, s - 2 * (s - w)));
}
}
}

inline void addEdge(int u, int v) {
E[e].v = v; E[e].x = l[u]; l[u] = e++;
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d", &n);
scanf("%s", S+1);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
for (int i = 1; i <= n; i++) {
dep[i] = 0;
dfs(i, 0);
int sum = 0;
for (int j = 1; j <= n; j++) {
if (S[j] == '1') {
sum += dep[j];
}
}
if (!lb[i]) ans = min(ans, sum / 2);
}
if (ans == inf) puts("-1");
else printf("%d\n", ans);
return 0;
}