DTOI-5 3-1 神树研究

题目背景/n/n——‘太阳’这种东西，以前似乎是存在的。/n/n传说是这么讲的——白色的火焰发出闪耀的光芒，天空则是清澄无比的蔚蓝。/n/n据说诸神与其创造物所掀起的‘大战’，使得大地化为焦土，灰烬遮蔽了苍穹。/n/n灰烬冲击到天上流动的星辰之力——精灵回廊，发出了光芒，将天空染成红色。/n/n而那样的红色，覆盖了仍然持续着互相残杀的每一块土地。/n/n或者那是这个星球本身发出的悲鸣与流出的鲜血吧……/n/n血色的天空上，只有——蓝色的灰飘然落下。/n/n~~回来吧3579，我最骄傲的信仰/ll~~/n/n## 题目描述/n/n里克在视线可及的范围内发现了一颗古老的‘神树’。/n/n神树是一颗树，树上有 $n$ 个含有魔法装置的位置。经过初步‘考察’，有 $n - 1$ 条魔法连接，第 $i(1 /leq i /leq n - 1)$ 条连接连接 $1 /leq u_i /neq v_i /leq n$ 两个魔法装置。这两个装置可以相互双向地在 $1$ 单位时间内通行，保证仅由这 $n - 1$ 条连接，每个魔法装置都可以相互到达。/n/n此外，有 $n - 1$ 条特殊连接，对于每个魔法装置 $i /in [2, n]$，可以瞬间传送到第 $1$ 个魔法装置，花费 $0$ 单位时间。特殊连接总共只能使用一次。/n/n里克初始在魔法装置 $1$ 处。现在，给出这棵‘神树’的结构，里克想要在若干时间内研究尽可能多的魔法装置。我们假定，研究一个魔法装置只需要到达该装置处，并且不需要花费额外时间。/n/n里克想让你尽快计算出，对所有 $k /in [1, n]$，如果要恰好研究 $k$ 个不同的魔法装置，并且随之返回魔法装置 $/bm 1$，最少应花费多少时间。/n/n## 输入格式/n/n第一行，一个整数 $n$。/n/n接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$。/n/n## 输出格式/n/n共 $n$ 行，第 $i$ 行一个整数表示 $k = i$ 的答案。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n5/n1 2/n1 3/n2 4/n2 5/n/n/n### 样例输出 #1/n/n/n0/n1/n2/n4/n6/n/n/n## 样例 #2/n/n### 样例输入 #2/n/n/n见下发的 hope/hope2.in/n/n/n### 样例输出 #2/n/n/n见下发的 hope/hope2.ans/n/n/n## 提示/n/n**【样例解释 $/bm 1$】/n/n+ $k = 1$ 时，里克只需要呆在装置 $1$ 处。/n+ $k = 2$ 时，里克的路径可以是 $1 /rightarrow 2 /Rightarrow 1$。/n+ $k = 3$ 时，里克的路径可以是 $1 /rightarrow 2 /rightarrow 4 /Rightarrow 1$。/n+ $k = 4$ 时，里克的路径可以是 $1 /rightarrow 2 /rightarrow 4 /Rightarrow 1 /rightarrow 3/rightarrow 1$。/n+ $k = 5$ 时，里克的路径可以是 $1 /rightarrow 3/rightarrow 1 /rightarrow 2 /rightarrow 5 /rightarrow 2 /rightarrow 4 /Rightarrow 1$。/n/n【样例解释 $/bm 2$】/n/n这组数据满足测试点编号 $13 /sim 20$ 的性质。/n/n【数据规模与约定】**/n/n| 测试点编号 | 特殊限制 || :--------: | :------: || $1 /sim 2$ | $n = 3$ || $3 /sim 4$ | $n = 5$ || $5 /sim 6$ | $n = 100$ || $7 /sim 8$ | $n = 1000$ || $9 /sim 10$ | $u_i = 1, v_i = i + 1$ || $11 /sim 12$ | $u_i = i, v_i = i + 1$ || $13 /sim 20$ | 无特殊限制 |对于所有数据，$1 /leq n /leq 10^5$，$1 /leq u_i, v_i /leq n$。/n/n写一个C++代码内容：思路：树形DP/n/n首先考虑如果只需要研究 $k$ 个魔法装置而不需要返回，那么可以用树形 DP 解决。/n/n设 $f_{i, j}$ 表示在以 $i$ 为根的子树中，选择 $j$ 个魔法装置的最小时间。/n/n转移方程为：/n/n$$f_{i, j} = /min/{f_{i, j}, f_{v, j - 1} + w_{u, v} + 1/}$$/n/n其中 $u, v$ 是 $i$ 的子节点，$w_{u, v}$ 是它们之间的距离。/n/n注意到这个 DP 转移方程中，$f_{i, j}$ 只依赖于 $f_{v, j - 1}$，因此可以使用滚动数组进行优化，使空间复杂度降为 $O(n)$。/n/n接下来考虑如何处理返回 $1$ 这个魔法装置的情况。注意到这个要求是恰好研究 $k$ 个魔法装置，而不是至少研究 $k$ 个魔法装置。因此，对于每个 $k$，我们可以枚举在以 $1$ 为根的子树中选择了多少个魔法装置，以及在其他子树中选择了多少个魔法装置，然后计算出对应的最小时间，取最小值即可。/n/n具体来说，设 $g_{i, j}$ 表示在以 $i$ 为根的子树中，选择 $j$ 个魔法装置并返回到 $1$ 的最小时间。设 $h_{i, j}$ 表示在以 $i$ 为根的子树之外，选择 $j$ 个魔法装置并返回到 $1$ 的最小时间。则可以得到如下的转移方程：/n/n$$g_{i, j} = /min/{g_{i, j}, f_{i, j} + 1/}$$/n/n$$h_{i, j} = /min/{h_{i, j}, h_{fa_i, j - k} + g_{i, k}/}$$ /n/n其中 $fa_i$ 表示 $i$ 的父节点，$k$ 的范围为 $[0, j]$。/n/n注意到这个 DP 转移方程中，$h_{i, j}$ 只依赖于 $h_{fa_i, j - k}$ 和 $g_{i, k}$，因此可以使用滚动数组进行优化，使空间复杂度降为 $O(n)$。/n/n时间复杂度：$O(n^2)$。/n/n空间复杂度：$O(n)$。/n/n代码：