No.1174 盆栽の剪定
tatyam問題文
tatyam は盆栽を育てるのが得意です。
tatyam は盆栽を $1$ 鉢持っています。
盆栽は $N$ 頂点の二分木で表され、各頂点には $1$ 〜 $N$ の番号がついています。
頂点 $1$ が根で、頂点 $i$ $(i ≠ 1)$ の親は頂点 $\left\lfloor \dfrac{i}{2} \right\rfloor$ です。
また、各頂点には盆栽の価値に関わる重み $A_i$ があり、盆栽の価値 $V$ は次のように表されます。
- $L_i$ = 頂点 $2i$ とその子孫の重みの合計 (存在しない場合 $0$ )
- $R_i$ = 頂点 $2i + 1$ とその子孫の重みの合計 (存在しない場合 $0$ )
- $V$ = $\displaystyle\sum_{1≤i≤N}|L_i-R_i|$
- 盆栽の辺を $1$ つ選び削除する。頂点 $1$ が含まれない連結成分は消える。
入力
$N$ $A_1\ \ \dots\ \ A_N$
- $1 ≤ N ≤ 10^5$
- $0 ≤ A_i ≤ 10^9$
- 入力は全て整数
出力
操作を $0$ 回以上行うときの価値の最大値を求めてください。 最後に改行してください。
サンプル
サンプル1
入力
7 7 0 4 6 4 3 5
出力
14
初期状態では、
$L_1 = 10 , R_1 = 12$
$L_2 = 6 , R_2 = 4$
$L_3 = 3 , R_3 = 5$
であり、価値は $6$ です。
頂点 $1 , 3 , 7$ のみにすると価値が $14$ になり、これが最大です。
サンプル2
入力
12 0 1 0 2 3 0 0 0 4 5 6 7
出力
41
初期状態のままですでに最大であり、剪定をする必要はありません。
サンプル3
入力
15 0 4 0 0 2 0 4 1 1 0 0 2 2 0 0
出力
11
初期状態では価値は $0$ ですが、頂点 $7 , 8 , 13 , 14 , 15$ を削除することによって 価値が $11$ になります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。