問題一覧 > 通常問題

No.1174 Pruning the Bonsai

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : tatyam
お気に入りにしたユーザー ProblemId : 4980 / 自分の提出
問題文最終更新日: 2020-08-18 01:31:54
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

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|$
tatyam wants to prune this bonsai skillfully to increase its value. tatyam can repeatedly perform the following operation.

  • Choose $1$ edge of the bonsai and delete it. The connected component that does not contain vertex $1$ disappears.
Find the maximum value achievable by performing this operation $0$ or more times.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。