分数: 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