P15891 [COCI 2025/2026 #6] Skijanje

Skier Mia spent a day at an unusual ski resort. The resort consists of $n$ apres-ski locations (hereafter: apres) connected by slopes such that they form a connected tree rooted at the apres labeled $1$. Each slope is directed from the apres with a smaller number to the apres with a larger number. The tree is defined as follows: for each apres $i > 1$, it is known from which apres $p_i$ ($p_i < i$) one arrives at it, i.e., its parent in the tree is known. This uniquely determines all slopes (slope $i$ leads to the apres labeled $i$). During the day, Mia skied each slope exactly once and for each slope remembered its fun factor $z_i$ and speed $b_i$. At the end of the day, Mia wants to ski down once more. Since Mia is very tired from skiing all day, she will choose a run consisting of at most $k$ consecutive slopes. The run must follow the direction of the slopes (from apres with smaller numbers to those with larger numbers). After finishing the run, a helicopter will pick her up and take her home. For any chosen run, we define its hecticness as follows. Let: - $z_{\text{first}}$ be the fun factor of the first slope in the run - $z_{\text{last}}$ be the fun factor of the last slope in the run - $b_i$ be the speeds of all slopes in that run Then the hecticness of the run is: $$ z_{\text{last}} \cdot \left(z_{\text{last}} + \sum b_i\right) + z_{\text{first}}^2. $$ In the case $k = 1$, the formula remains unchanged, and $\text{first} = \text{last}$ holds. Your task is to determine the maximum hecticness of a run that Mia can ski.

The first line contains natural numbers $n, k$ ($1 \le k \le n \le 3 \cdot 10^5$), as described in the problem statement. The second line contains $n - 1$ integers, where the $i$-th number represents from which apres one can reach the apres labeled $i + 1$ ($1 \le p_i \le i$). The third line contains $n - 1$ integers, where the $i$-th number represents the fun factor of the $(i + 1)$-th slope ($1 \le z_i \le 10^5$). The fourth line contains $n - 1$ integers, where the $i$-th number represents the speed of the $(i + 1)$-th slope ($-10^5 \le b_i \le 10^5$).

In the first and only line, output a single number - the maximum hecticness of a run that Mia can ski.

**Clarification of the first example**: Since $k = 1$, it follows that the maximum hecticness of a run is equal to the maximum hecticness among the individual slopes. The slopes have hecticness values of $80, 44, 200,$ and $119$. The maximum hecticness is $200$. **Scoring** | Subtask | Points | Constraints | |:-------:|:------:|--------------------------------------------------| | 1 | 14 | $n \le 1000$ | | 2 | 23 | For each $1 \le i < n$ it will hold that $z_i = 1$ and $b_i > 1$. | | 3 | 35 | $n \le 50000$ | | 4 | 38 | No additional constraints. |