問題一覧 > 通常問題

No.1524 Upward Mobility

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : aspi / テスター : 沙耶花 NatsubiSogan 👑 Nachia
お気に入りにしたユーザー ProblemId : 6204 / 自分の提出
問題文最終更新日: 2021-05-21 00:18:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 297 (順位表) の他の問題:

Problem Statement

You are given a rooted tree with $N$ vertices numbered from $1$ to $N$. The root is vertex $1$, and the parent of vertex $i\ (2 \leq i \leq N)$ is vertex $p_i$.

Integers $a_i,b_i$ are written on vertex $i\ (1 \leq i \leq N)$ of this tree.

You decide to choose $0$ or more vertices and erase both $a_i,b_i$ written on the chosen vertices. However, since you are highly ambitious, you want the following condition to be satisfied for every leaf $v$ of the tree.

  • Consider the simple path from vertex $1$ to vertex $v$.
  • When the values $a_i$ written on the vertices of the path are arranged in order along the path (ignoring vertices whose $a_i$ has been erased), the sequence is monotonically increasing.

When you appropriately choose the vertices on which to erase $a_i,b_i$ while satisfying the condition, what is the maximum possible sum of $b_i$ written on the remaining vertices?

Input

$N$
$p_2\ p_3\ \ldots \ p_N$
$a_1\ a_2\ \ldots \ a_N$
$b_1\ b_2\ \ldots \ b_N$
  • All inputs are integers.
  • $2 \leq N \leq 10^5$
  • $1 \leq p_i < i$
  • $1 \leq a_i \leq N$
  • $a_1,a_2,\cdots,a_N$ are pairwise distinct.
  • $1 \leq b_i \leq 10^9$

Output

Print on $1$ line the maximum sum of $b_i$ when the integers on the vertices are erased appropriately.

Print a newline at the end.

Sample

Sample 1
Input
6
1 1 2 3 2
5 3 6 2 4 1
2 1 8 7 8 5
Output
20

Sample 2
Input
10
1 1 3 2 4 1 6 8 6
1 3 6 7 5 10 2 9 8 4
18 93 98 53 42 34 61 73 91 42
Output
456

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。