No.1524 Upward Mobility
タグ : / 解いたユーザー数 15
作問者 :
aspi
/ テスター :
沙耶花
Nachia
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もしくは右上の雲マークをクリックしてアカウントを作成してください。