No.1174 Pruning the Bonsai
タグ : / 解いたユーザー数 12
作問者 :
tatyam
Problem Statement
tatyam is good at growing bonsai.
tatyam owns $1$ bonsai.
The bonsai is represented by a binary tree with $N$ vertices, numbered $1$ to $N$.
Vertex $1$ is the root, and the parent of vertex $i$ $(i ≠ 1)$ is vertex $\left\lfloor \dfrac{i}{2} \right\rfloor$.
Each vertex also has a weight $A_i$ related to the value of the bonsai, and the value $V$ of the bonsai is expressed as follows.
- $L_i$ = the sum of the weights of vertex $2i$ and its descendants ( $0$ if it does not exist)
- $R_i$ = the sum of the weights of vertex $2i + 1$ and its descendants ( $0$ if it does not exist)
- $V$ = $\displaystyle\sum_{1≤i≤N}|L_i-R_i|$
- Choose $1$ edge of the bonsai and delete it. The connected component that does not contain vertex $1$ disappears.
Input
$N$ $A_1\ \ \dots\ \ A_N$
- $1 ≤ N ≤ 10^5$
- $0 ≤ A_i ≤ 10^9$
- All inputs are integers.
Output
Output the maximum value achievable by performing the operation $0$ or more times. Print a newline at the end.
Sample
Sample 1
Input
7 7 0 4 6 4 3 5
Output
14
In the initial state,
$L_1 = 10 , R_1 = 12$
$L_2 = 6 , R_2 = 4$
$L_3 = 3 , R_3 = 5$
and the value is $6$.
Keeping only vertices $1 , 3 , 7$ makes the value $14$, which is the maximum.
Sample 2
Input
12 0 1 0 2 3 0 0 0 4 5 6 7
Output
41
The initial state is already the maximum, so no pruning is needed.
Sample 3
Input
15 0 4 0 0 2 0 4 1 1 0 0 2 2 0 0
Output
11
The value is $0$ in the initial state, but deleting vertices $7 , 8 , 13 , 14 , 15$ makes the value $11$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。