修正について

2024.2/13 17:50時点: 入出力例の詳細に誤りがあったので修正しました。

Story

🍉

greenrate君とnum016君はおもちゃで存分に遊びました。面白いですねこれ。

…その頃。summerrate君は雪が大嫌いです。 雪が冷たくて、寒くなるためです。

「matcharateもwhiteもgreenrateもnum016もみんなそろいも揃って雪を楽しみやがって…早く夏になれ！！」

そう言ってると、matcharate君とwhiteさんはおっきなおっきな雪だるまを抱えながら、こっちにやってきます。 summerrate君の地獄耳から、matcharate君たちのことがこう聞こえました。

「みんな街は雪玉を嫌ってやがる…いい気味だ。もっと雪玉を嫌いにさせてやる！！！！」

問題

matcha国には雪が降っています。その雪を使って雪だるまを $K$ 個作りました。
左から $i\ (1\le i\le K)$ 番目の雪だるまの大きさは数値 $U_i$ で表されます。

今からmatcharate君はこの $K$ 個の中から雪だるまを $1$ つだけ選びます。
トラックが通る街の候補は $N$ 個あり、街と街を相互に繋ぐ道は $N-1$ 本あります。
それぞれ街には $1,2,\dots ,N$ と番号づけられており、$j\ (1\le j\le N-1)$ 番目の道は街 $A_j$ から街 $j+1$ に繋いでいます。

さらにそれぞれの街はなるべく大きな雪だるまを持って街を訪れて欲しくないと思っています。
厳密に言うと街 $x\ (2\le x\le N)$ を訪れる際に、運んでいる雪だるまの大きさが $C_x$ 以下である必要があります。

また各道の距離はすべて $1$ です。$k=1,2,\dots ,K$ に対する次の問に対し、答えを求めてください。

• $k$ 番目の雪だるまを選びました。この雪だるまを、道を通りながら最も遠い街に運ぼうと思っています。
  街 $1$ から運ぶとしたとき、距離の合計の最大値はいくつですか？

ただしそれぞれの道は $1$ 度しか通れないものとします。

入力

入力は以下の形式で与えられる。

制約

• $1\le K\le 1000$
• $1\le U_i\le 10^9$
• $2\le N\le 300$
• $1\le A_i\le i\ (1\le i\le N-1)$
• $1\le C_i\le 10^9\ (2\le i\le N)$
• 入力はすべて整数

出力

$K$ 行出力せよ。$i$ 行目には $k=i$ としたときの答えを出力せよ。

入出力例

5
10 20 5 10 30
7
1 2 2 4 4 1
20 10 40 5 10 15

3
2
3
3
0

例えば $k=2$ の時、次のように街を経由しながら移動すると $2$ 本の道をたどっていくことでたどりつくことができます。

• 街 $1$ から街 $2$ に移動する
• 街 $2$ から街 $4$ に移動する

街 $1$ から街 $3$ または街 $7$ に移動するとした際、$U_2=20$ から $C_3=10\lt 20$ また $C_7=15\lt 20$ より、この移動をすることはできません。

$k=5$ の時は $1$ つも街を経由することはできません。よって道を $1$ つも通過することはできません。