华师一附中OI组

标题: 2269: 花花的聚会 [打印本页]

作者: admin 时间: 2021-10-27 14:53
标题: 2269: 花花的聚会
题目描述
花花住在H 国。H 国有n 个城市，其中1 号城市为其首都。城市间有n -1 条单向道路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都。事实上，从任何一个城市走到首都的路径是唯一的。
过路并不是免费的。想要通过某一条道路，你必须使用一次过路券。H 国一共有m 种过路券，每张过路券以三个整数表示：v k w：你可以在城市v 以价格w 买到一张过路券。这张券可以使用k 次。这意味着，拿着这张券通过了k 条道路之后，这张券就不能再使用了。
请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券，并且在所在的城市再买一张。
花花家在首都。他有q 位朋友，他希望把这些朋友们都邀请到他家做客。所以他想要知道每位朋友要花多少路费。他的朋友们都很聪明，永远都会选择一条花费最少的方式到达首都。
花花需要准备晚餐去了，所以他没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？
输入格式
输入的第一行包含两个空格隔开的整数n 和m，表示H 国的城市数量和过路券的种数。
之后的n -1 行各自包含两个数ai 和bi，代表城市ai 到城市bi 间有一条单向道路。
之后的m 行每行包括三个整数vi; ki 和wi，表示一种过路券。
下一行包含一个整数q，表示花花朋友的数量。
之后的q 行各自包含一个整数，表示花花朋友的所在城市。

输出格式
输出共q 行，每一行代表一位朋友的路费。
输入样例复制
7 7
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
3
5
6
7
输出样例复制
10
22
5

数据范围与提示
对于第一位朋友，他在5 号城市只能购买一种过路券，花费10 元并且可以使用3 次。这足够他走到首都，因此总花费是10 元。
对于第二位朋友，他在6 号城市只能购买20 元的过路券，并且只能使用一次。之后，他可以在3 号城市购买2 元，可以使用3 次的过路券走到首都。总花费是22 元。
对于第三位朋友，他在7 号城市可以购买两种过路券。他可以花3 元买一张可以使用2次的券，然后在3 号城市再买一张2 元，可以使用3 次的券，走到首都。总花费是5 元，而且其他的购买方式不会比这种更省钱。

作者: admin 时间: 2021-10-27 14:53
题意翻译
有一棵 n 个节点的有根树，在某些节点 vi，可以选择花费 wi 的代价，向上跳 [1, ki] 步。
现有 q 个询问，询问一些节点跳到根的最少代价。

解法一
对于每个询问，暴力枚举所有可能的向上跳的方案，从而得到最少代价。在枚举过程中可加入各种剪枝。
期望得分 40 分。

解法二
对于每个询问，我们可以贪心地选择向上跳的方案。并使用相关的数据结构来提升效率。
期望得分 0-100 分。

解法三
不难发现，我们可以用动态规划的思想来解决这个问题。记 f(u) 为 u 跳到根的最少代价。
则不难得出转移方程：f(u) = min{f(v) + wi}，其中 v 是 u 的祖先，且存在一种车票 ui, wi, ki并满足 dep(u) − dep(v) ≤ ki。这个DP方程的边界条件为 f(root)= 0。这样对于每种车票，我
们可以暴力枚举所有合法的 v，从而求得答案v。
时间复杂度为 O(mn)，期望得分 60-80 分。

解法四
考虑优化解法三的DP转移。事实上我们只需在较快的时间内求得树上某一段区间的min{f(u)}，即可较好地解决这个问题。而维护树上区间最值有树链剖分、动态树等许多数据
结构能够胜任。在这里我们考虑用倍增的思想，维护u往上跳 2i 步到的祖先 v 和 u 到 v 这一段 f 值的最小值，这样我们对于每一个节点 u 可以在 O(logn) 的时间内求得 min{f(u)}。
时间复杂度为 O(nlogn)，期望得分 100 分。

作者: admin 时间: 2021-10-27 14:53
2 花花的聚会
2.1 题意简述
有一棵 n 个节点的有根树，在某些节点 vi，可以选择花费 wi 的代价，向上跳 [1, ki
] 步。
现有 q 个询问，询问一些节点跳到根的最少代价。
2.2 解法一
对于每个询问，暴力枚举所有可能的向上跳的方案，从而得到最少代价。在枚举过程中可
加入各种剪枝。
期望得分 40 分。
2.3 解法二
对于每个询问，我们可以贪心地选择向上跳的方案。并使用相关的数据结构来提升效率。
期望得分 0-100 分。
2.4 解法三
不难发现，我们可以用动态规划的思想来解决这个问题。记 f[u] 为 u 跳到根的最少代价。
则不难得出转移方程：f[u] = min{f[v] + wi}，其中 v 是 u 的祖先，且存在一种车票 ui
, wi
, ki
并满足 dep[u] − dep[v] ≤ ki。这个DP方程的边界条件为 f[root] = 0。这样对于每种车票，我
们可以暴力枚举所有合法的 v，从而求得答案。
时间复杂度为 O(mn)，期望得分 60-80 分。
2.5 解法四
考虑优化解法三的DP转移。事实上我们只需在较快的时间内求得树上某一段区间的
min{f[u]}，即可较好地解决这个问题。而维护树上区间最值有树链剖分、动态树等许多数据
结构能够胜任。在这里我们考虑用倍增的思想，维护 u 往上跳 2
i 步到的祖先 v 和 u 到 v 这一
段 f 值的最小值，这样我们对于每一个节点 u 可以在 O(logn) 的时间内求得 min{f[v]}。
时间复杂度为 O(nlogn)，期望得分 100 分。

欢迎光临华师一附中OI组 (http://hsyit.cn/)