P15891 [COCI 2025/2026 #6] 滑雪 / Skijanje

滑雪者米娅在一个不寻常的滑雪场度过了一天。滑雪场由 $n$ 个滑雪后休息点（以下简称“休息点”）组成，它们由雪道连接，形成一棵以 $1$ 号休息点为根的有根树。每条雪道从编号较小的休息点指向编号较大的休息点。 这棵树定义如下：对于每个 $i > 1$ 的休息点，已知从哪个休息点 $p_i$（$p_i < i$）可以到达它，即它在树中的父节点已知。这唯一确定了所有的雪道（第 $i$ 条雪道通向编号为 $i$ 的休息点）。 白天，米娅每条雪道恰好滑过一次，并记住了每条雪道的乐趣系数 $z_i$ 和速度 $b_i$。 一天结束时，米娅想再滑一次。由于滑了一整天非常疲惫，她会选择一条由 **最多** $k$ 条 **连续** 雪道组成的滑行路线。该路线必须沿着雪道的方向（从编号较小的休息点向编号较大的休息点滑行）。滑完路线后，直升机会接她回家。 对于任意选择的路线，其 **紧张度** 定义如下。设： - $z_{\text{first}}$ 为路线上第一条雪道的乐趣系数； - $z_{\text{last}}$ 为路线上最后一条雪道的乐趣系数； - $b_i$ 为该路线上所有雪道的速度。 则该路线的紧张度为： $$ z_{\text{last}} \cdot \left(z_{\text{last}} + \sum b_i\right) + z_{\text{first}}^2. $$ 当 $k = 1$ 时，公式保持不变，此时 $\text{first} = \text{last}$。 你的任务是确定米娅能滑出的路线的最大紧张度。

第一行包含自然数 $n, k$（$1 \le k \le n \le 3 \cdot 10^5$），含义如题目描述所述。 第二行包含 $n-1$ 个整数，其中第 $i$ 个数表示从哪个休息点可以到达编号为 $i+1$ 的休息点（$1 \le p_i \le i$）。 第三行包含 $n-1$ 个整数，其中第 $i$ 个数表示第 $i+1$ 条雪道的乐趣系数（$1 \le z_i \le 10^5$）。 第四行包含 $n-1$ 个整数，其中第 $i$ 个数表示第 $i+1$ 条雪道的速度（$-10^5 \le b_i \le 10^5$）。

输出一行一个整数，表示米娅能滑出的路线的最大紧张度。

**第一个样例的解释**：由于 $k = 1$，最大紧张度等于各条雪道紧张度的最大值。各条雪道的紧张度分别为 $80, 44, 200$ 和 $119$，最大紧张度为 $200$。 **计分方式** | 子任务 | 分值 | 约束条件 | |:-------:|:------:|--------------------------------------------------| | 1 | 14 | $n \le 1000$ | | 2 | 23 | 对于所有 $1 \le i < n$，满足 $z_i = 1$ 且 $b_i > 1$。 | | 3 | 35 | $n \le 50000$ | | 4 | 38 | 无额外限制。 | 翻译由 DeepSeek V3.2 完成