← 返回题目列表

AtCoder · joi2026_semifinal_d

D. 漂流

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

配点: 100 点

問題文

在JOI国家 有 N 个城市,每个城市有 它们的编号最大为 1 当编号达到 N 。 这些城市之间 N-1 有一条书路, 它们的编号最大为1 当编号达到 N - 1。 路 i (1 \leqq i \leqq N-1) 是一座城市 P_i (P_i \leqq i)和城市 i + 1 是相互连接的。 城市 保证您可以通过多条道路从 1 前往任何城市。 另外,在JOI国家,还有与道路平行的河流。 N - 1 河里有书。 它们的编号最大为 1 当编号达到 N - 1 。 河 i (1 \leqq i \leqq N-1)就是这样 它与 i 平行,并且城市 P_i 从市区出发 它朝 i + 1 方向流动。

N 每个城镇都有 1 灯一盏一盏地摆放着。 每盏灯都有实力已定义。 城市 t (1 \leqq t \leqq N处的灯强度为 当 l 时,从那个城市 l 这座可以通过短路到达的城市被这盏灯照亮。 开始时,灯强度均为 0 并且没有城市被照亮。

你河漂流请计算 0 您可以根据需要多次执行此操作。 河的下游就是城市 从您所在的状态 1 开始,首先 1 中灯的强度 1 增加。 然后,按顺序重复以下操作。

  1. 决定是否结束河流行程。然而,如果没有河流从你当前所在的城市流出,这将永远结束。
  2. 继续顺流而下时,沿着从您当前所在城镇流出的河流行驶。 1 选择一个并沿着该河的水流移动。你搬到的城市的灯光强度 1 增加。

沿着城镇周围的河流而下 如果它以 t 结束,则此下游行程的成本为 C_t 。 你顺河而下 0 我想多次执行此操作,以便每个城市都被其中一盏灯照亮。 最重要的是,有必要最大限度地降低下游的总成本。

给定道路和成本信息,编写一个程序,找出沿河行驶的最低总成本,以便所有城镇都被某种类型的灯照亮。


入力

输入是按以下格式从标准输入给出的。

N
P_1 P_2 \cdots P_{N-1}
C_1 C_2 \cdots C_N

出力

标准输出是顺流而下的总成本的最小值,以便每个城市都被一盏灯照亮。 1 行。


制約

  • 2 \leqq N \leqq 700.
  • 1 \leqq P_i \leqq i (1 \leqq i \leqq N-1).
  • 1 \leqq C_t \leqq 10^9 (1 \leqq t \leqq N).
  • 所有输入值均为整数。

小課題

  1. (13 点) N \leqq 8.
  2. (25 点) N \leqq 100.
  3. (7 点) P_i = 1 (1 \leqq i \leqq N-1).
  4. (11 点) P_i = i (1 \leqq i \leqq N-1).
  5. (16 点)全部 i (1 \leqq i \leqq N),P_j = i 变为 j (1 \leqq j \leqq N-1)是 2 個以下.
  6. (28 点)没有额外的限制。

入力例 1

5
1 2 2 4
10 4 8 9 5

出力例 1

9

1 第一次顺流而下时, 选择 1 并 在 2 处结束河流下降。 此时的城市 1, 2 处的灯强度 1 增加,成本 4 。 2 第一次顺流而下时, 选择 1, 3, 4 并 在 5 处结束河流下降。 此时的城市 1, 2, 4, 5 处的灯强度 1 增加,成本 5 。

运行后,该市 1, 2 处的灯强度为 2,街 3 处的灯强度为 0,街 4, 5 处的灯强度为 1 变为。 城市 1, 2, 3, 4 是一座城市 优势在于 2 在 2 灯下,城市 由 5 是一座城市 优势在于 5 在 1 灯照亮。因此,通过这些操作,所有的城市都将被某种灯照亮。 在这种情况下,总成本是 由于成本小于 4 + 5 = 9 。 9 无法满足条件,9 。

此输入示例是一个小作业。 1, 2, 5, 6 满足约束。


入力例 2

9
1 1 1 2 5 5 5 3
100 70 80 90 60 30 40 50 30

出力例 2

90

川 1, 4, 5 穿越城市 河流之旅结束于 6 执行 2 回,川 2, 8 穿越城市 河流之旅结束于 9 执行 1 次。 手术后,市 1 处的灯强度为 3,街 2, 5, 6 处的灯强度为 2,街 3, 9 处的灯强度为 1,街 4, 7, 8 处的灯强度为 0 变为。 通过这些行动,每个城市都将被一盏灯照亮。 在这种情况下,总成本是 30 \times 2 + 30 = 90 。90 无法满足条件,90 。

此输入示例是一个小作业。 2, 6 满足约束。