← 返回题目列表

AtCoder · awc0098_e

E. 水道维护

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

分数: 433 分

问题陈述

有一个区域由 N 定居点。该区域路网呈树状结构,有沉降 1 作为根(中心枢纽)。每个定居点 i (2 \leq i \leq N) 有家长定居 P_i,以及结算 i 和结算 P_i 由道路直接连接。有 N - 1 道路总数。

已决定沿每条道路开发一条水路。每条水道的建设所需的基本建设成本为 1。此外,对于每一个航道建设, 必须选择由相应道路连接的两个定居点的 正好一个 作为责任定居点,并由该定居点承担施工。即连接聚落的道路沿线的水路建设 i 和结算 P_i,任一结算 P_i 或结算 选择 i 负责。每条水道都必须分配给其中一个定居点。

这里,每个定居点的水道 i 只能负责那些对应于有结算的道路 i 作为端点。具体来说,如果结算 i 不是根,符合条件的水道是“连接聚落的边缘”的水道 i 及其父级 P_i“和”连接沉降的边 i 及其每个子定居点。”用于结算 1 (根),没有父级,只有通往子级定居点边缘的水道才符合条件。

对于每个结算 i (1 \leq i \leq N),一个 施工能力 C_i 和 附加成本系数 W_i 已定义。让 m_i 为分配给定居点的水道建设数量 i。如果 m_i 最多是 C_i,不会产生额外费用。然而,如果 m_i 超过 C_i,额外费用 每条超额航道都会产生 W_i 。即结算时产生的额外费用 i is W_i \times \max(0,\, m_i - C_i).

的 总成本 是所有水道的基本建设成本之和(始终 N - 1) 加上所有结算所产生的额外费用总和:

\displaystyle (N - 1) + \sum_{i=1}^{N} W_i \times \max(0,\, m_i - C_i)

确定最优选择每条水道的责任结算时的最小总成本。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
  • 0 \leq C_i \leq N (1 \leq i \leq N)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数。

输入

N
P_2 P_3 \ldots P_N
C_1 W_1
C_2 W_2
\vdots
C_N W_N
  • 第一行给出了定居点的数量 N.
  • 第二行给出 P_2, P_3, \ldots, P_N,代表结算的父结算 2, 3, \ldots, N,用空格分隔。
  • 如下 N 行, i- 第行 (1 \leq i \leq N) 给出了施工能力 C_i 及附加成本系数 W_i 结算 i,用空格分隔。

输出

在一行中输出最小总成本。


示例输入 1

4
1 1 2
1 3
0 5
2 2
0 4

示例输出 1

7

示例输入 2

5
1 1 1 1
0 10
1 1
0 7
2 3
0 2

示例输出 2

13

示例输入 3

12
1 1 2 2 3 3 4 4 6 6 10
1 8
2 3
0 10
1 6
0 2
2 5
1 9
0 4
3 1
1 7
0 3
2 6

示例输出 3

13

示例输入 4

30
1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 10 10 11 12 13 14 15 16 17 18 20 24
1 100
3 5
0 20
2 7
1 12
3 4
0 50
1 9
2 6
0 30
4 2
1 15
0 11
2 8
1 25
0 3
2 18
1 10
3 1
0 40
1 13
2 5
0 17
1 22
3 6
0 14
2 9
1 16
0 19
4 2

示例输出 4

115

示例输入 5

2
1
0 1000000000
2 1

示例输出 5

1