题意
给一棵无向树，问最少去掉几条边可以形成一个大小为k的子树，多次询问。n ≤ 3000，m ≤ n
输入输出
输入一棵树和m个询问，输出m个数字，表示答案，如果不可能，输出-1。
样例
1
2
3
4
5
6
7
8
9
10
| 7
1 2
1 3
2 4
2 5
3 6
3 7
2
2
3
|
解法
为了简化问题，我们先随便取一个节点作为树根，假设这棵树是一个有向树。用 表示以 为节点的子树， 表示这个子树的大小。
考虑暴力的动态规划做法。对于一个节点和任意整数满足 ， 表示要让包含 的联通分量的大小恰好为 i 的话我们最少需要删除的边的个数。显然，如果我们有所有的 的值，那么我们就能在 时间内回答一次询问。
如果 是一个叶子结点，那么以 为根的子树只有一个节点，所以 。接着，我们假设一个节点 有 个孩子 ，并且对于所有 和 ，所有的 都已经被计算过了，那么要怎么计算出 的每一个值呢？
首先描述以 为根的更大的子树 ，它表示以 为根，取前 个孩子的子树（下图为）。设 表示树 中要包含节点 的连通分量恰好为 最少需要删除的边数。我们观察到 。
Barricades
我们从 开始。 是一个只有一个节点的树，所以 。现在，我们准备去为更大的 计算数组 的值。可以列出递推方程： 其中 ，.
这个方程的每一步包含两种情况，一种是删除边 ，不取 整棵子树；另一种情况是不删除这条边，枚举在 和 中所有的删除边数相加等于 的可能的最小值。
分析一下复杂度。显然，最耗时的操作是求出所有的 ，它的复杂度看上去是 的，因为对于 个数组 我们执行了 次操作。实际上，我们可以证明它的复杂度是 的。
引理：对于一个节点 ，我们需要求出所有 的值（ 是子树 中的节点），只需要执行 次操作。
证明：如果 是一个叶子节点，那么引理显然成立。否则，假设节点 恰好存在 个孩子节点 ，设 ，当执行合并第 个孩子节点的操作时，我们要对所有可能的 和 遍历 和 ， 的值有 种可能， 有 种可能。所以一共需要执行： 次操作。所以，计算出数组 中所有的元素需要 次操作。把所有操作加起来，要计算出 中包含的所有节点 的 需要的时间为： 这个证明也有另一个组合意义上的解释。由于一共需要执行 次操作，我们可以把这个数字看作一个和以 为最近公共祖先的节点对的个数成正比的数，既然一棵树中的每一对点都只存在一个最近公共祖先，所以每一对点只会被计算一次，所以算出 数组的复杂度为 。
于是，我们就可以在 时间内解决整个问题。
需要注意的是，要获得 的复杂度，递推方程只能最多执行 个操作。特别是，我们不能允许自己在取 和 的时候迭代得太宽，如果我们在每次合并的时候产生 复杂度，那我们的算法就将需要 的最坏运行时间了。
代码
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
| #include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
const int maxn = 2005;
int n, u, v, m, k;
std::vector<int> T[maxn];
int t[maxn][maxn], siz[maxn];
int get_siz(int cur, int fa) {
siz[cur] = 1;
for (auto it: T[cur]) {
if (it != fa) {
siz[cur] += get_siz(it, cur);
}
}
return siz[cur];
}
void dfs(int cur, int fa) {
t[cur][1] = 0;
for (auto it: T[cur]) {
if (it != fa) {
dfs(it, cur);
for (int i = std::min(siz[cur]+siz[it], n); i >= 1; i--) {
int temp = t[cur][i] + 1;
for (int j = 1; j <= std::min(siz[cur], i); j++) {
temp = std::min(temp, t[cur][j] + t[it][i-j]);
}
t[cur][i] = temp;
}
}
}
}
int main(int argc, char *argv[]) {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
memset(t, 0x3f, sizeof t);
std::cin >> n;
for (int i = 0; i < n-1; i++) {
std::cin >> u >> v;
T[u].push_back(v);
T[v].push_back(u);
}
get_siz(1, -1);
dfs(1, -1);
std::cin >> m;
for (int i = 0; i < m; i++) {
std::cin >> k;
int ans = t[1][k];
for (int i = 2; i <= n; i++) {
ans = std::min(ans, t[i][k]+1);
}
std::cout << ans << '\n';
}
}
|
吐槽
写完交上去卡了空间。折腾了半天，然后我 assert(n<=2000) , 竟然没 RE，乱标数据范围，不讲武德，这好吗，这不好。
然后最后一组 T 了，我大力改了改选 a b 时候的迭代范围，卡过去了。题解的温馨提示诚不欺我。
虽然道理我都懂，但是这个真的不是 吗（（
发现这个东西实际上就是树上背包，我竟然连树上背包都不会！呜呜