← 返回题目列表

Codeforces · 1621/H

H. 火车和飞机

中文机器翻译题面 查看原题

一个城市的铁路网由 $$$n$$$ 个车站组成,并通过 $$$n-1$$$ 道路连接。这些车站和道路形成一棵树。车站$$$1$$$是市中心。对于每条道路,您都知道火车通过该道路所花费的时间。您可以假设火车不会在停靠站上花费时间。我们将 $$$dist(v)$$$ 定义为火车从 $$$v$$$ 车站到 $$$1$$$ 车站所花费的时间。

该铁路网分为多个区域,以 $$$k$$$ 大写拉丁字母命名。第$$$i$$$站的区域是$$$z_i$$$。市中心位于 A 区。对于所有其他车站,保证从该车站到市中心的道路上的第一个车站位于同一区或词典中名称较小的区。任何一条道路都完全归距市中心最远一端的区域所有。

游客很快就会到达机场,然后前往市中心。以下是从车站 $$$v$$$ 到车站 $$$1$$$ 的行程是如何发生的:

- 此时$$$0$$$,游客乘坐直接从车站$$$v$$$前往车站$$$1$$$的火车。行程将持续 $$$dist(v)$$$ 分钟。
- 游客可以随时购买任何区域子集的门票。 $$$i$$$ 区域的门票价格为 $$$pass_i$$$ 欧元。
- 自行程开始以来每 $$$T$$$ 分钟(即 $$$T、2T、\ldots$$$ 时刻)控制系统将扫描游客。如果在扫描时游客位于 $$$i$$$ 区域且没有 $$$i$$$ 区域门票,则他应支付 $$$fine_i$$$ 欧元。形式上,游客的区域是按以下方式确定的:如果游客在车站$$$1$$$,那么他已经在市中心,所以他不应该支付罚款。 如果游客在车站 $$$u \neq 1$$$,那么他就在 $$$z_u$$$ 区域。 如果游客从 $$$x$$$ 站移动到有公路直接连接的 $$$y$$$ 站,那么他就在 $$$z_x$$$ 区域中。 请注意,游客可以在同一区域多次缴纳罚款。

游客总是选择这样的方式来购买门票并支付罚款,以最小化旅行的总成本。令 $$$f(v)$$$ 为站 $$$v$$$ 的成本。

不幸的是,游客不知道不同区域的 $$$pass_i$$$ 和 $$$fine_i$$$ 的当前值,并且他忘记了机场的位置。他会问你 $$$3$$$ 类型的查询:

- $$$1$$$ $$$i$$$ $$$c$$$ — $$$i$$$ 区域的门票费用已更改。现在$$$pass_i$$$ 是$$$c$$$。
- $$$2$$$ $$$i$$$ $$$c$$$ — $$$i$$$ 区域的罚款成本已更改。现在$$$fine_i$$$ 是$$$c$$$。
- $$$3$$$ $$$u$$$ — 针对 $$$pass$$$ 和 $$$fine$$$ 的当前值解决以下问题: 给定站 $$$u$$$。考虑满足以下条件的所有站 $$$v$$$: $$$z_v = z_u$$$ 站 $$$u$$$ 位于从站 $$$v$$$ 到站 $$$1$$$ 的路径上。 计算所有此类车站 $$$v$$$ 的 $$$\min(f(v))$$$ 值,假设如下:游客持有 $$$z_u$$$ 车站区域的车票。

输入

第一行包含单个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — 车站数量。

接下来的 $$$n - 1$$$ 行包含三个整数 $$$v_i$$$、$$$u_i$$$、$$$t_i$$$ ($$$1 \leq v_i, u_i \leq n, 1 \leq t_i \leq 10^9$$$) - 第 $$$i$$$ 路的末端和火车通过这条路所需的时间。保证这条路形成一棵树。

下一行包含单个整数 $$$k$$$ ($$$1 \leq k \leq 26$$$) — 区域数量。

下一行包含 $$$n$$$ 符号 $$$z_1z_2 \ldots z_n$$$ — $$$z_i$$$ 是第 $$$i$$$ 站的区域名称。保证满足第二段的条件。

下一行包含 $$$k$$$ 整数 $$$pass_1$$$、$$$pass_2$$$、$$$\ldots$$$、$$$pass_k$$$ ($$$1 \leq pass_i \leq 10^9$$$) — 门票的初始成本。

下一行包含 $$$k$$$ 整数 $$$fine_1$$$、$$$fine_2$$$、$$$\ldots$$$、$$$fine_k$$$ ($$$1 \leq Fine_i \leq 10^9$$$) — 初始罚款。

下一行包含单个整数 $$$T$$$ ($$$1 \leq T \leq 10^9$$$) — 控制系统扫描之间的时间间隔。

下一行包含单个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含语句中描述的查询。保证在第一和第二类型的查询中 $$$i$$$ 是区域的正确名称(前 $$$k$$$ 大写拉丁字母之一)和 $$$1 \leq c \leq 10^9$$$,并且在第三类型的查询中 $$$1 \leq u \leq n$$$。

输出

对于第三种类型的每个查询,打印其答案。

示例

输入 #1

8
1 2 7
2 3 4
2 4 3
4 5 1
5 6 6
4 7 10
6 8 6
4
AABABBDB
11 12 10 42
16 15 15 30
4
6
3 2
1 A 10
3 3
2 A 3
3 7
3 6

输出 #1

0
10
6
6

注意

请注意,罚款可能比通票便宜。

示例中的铁路网。 A区车站和道路采用绿色,B区采用蓝色,D区采用红色。每条道路附近的整数为列车通过该道路所花费的时间。

在第一个查询中,机场可以位于车站 $$$2$$$ 附近或车站 $$$4$$$ 附近。在旅途中,游客将始终停留在A区。他已经拥有该区的通行证,所以答案是$$$0$$$。

第二次查询后,A区的通行证费用变成了$$$10$$$。

在第三个查询中,机场只能位于车站 $$$3$$$ 附近。最佳解决方案是购买 A 区的通行证。在旅行的前 $$$3$$$ 秒内,游客将在 B 区。然后他将移动到 A 区,并在骑行的第 $$$4$$$ 秒和第 $$$8$$$ 秒在那里接受扫描。因为他有这个区域的通行证,所以他不会支付罚款。

第四次查询后,A区罚款变为$$$3$$$。

在第五个查询中,机场只能位于车站 $$$7$$$ 和 $$$f(7) = 6$$$ 附近。

在第六个查询中,机场可以位于车站 $$$6$$$ 附近或车站 $$$8$$$ 附近。由于 $$$f(6)=9$$$ 和 $$$f(8)=6$$$ 答案是 $$$6$$$。