No.1215 都市消滅ビーム
レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 :
Thistle
/ テスター :
autumn-eel
タグ : / 解いたユーザー数 10
作問者 :
Thistle
/ テスター :
autumn-eel
問題文最終更新日: 2020-08-30 14:14:38
問題文
木構造になっている国があり、国を構成する $N$ 個の都市には $1, 2, \dots , N$ と番号が振られています。
都市同士は街道で双方向に結ばれており、 $i$ 番目の街道は都市 $A_i$ と都市 $B_i$ を結んでいます。
この国には$K$個の神殿があり、 $i$ 番目の神殿は都市 $C_i$ にあり、その価値は $D_i$ です。
この国が崇拝する神は、以下の操作で定義される値 $X$ が大きければ大きいほど喜びます。
- 神殿の価値の合計を $S$ とする。
- 国を都市 $1$ を根とした木とみたとき、全ての神殿がある都市のLCAを都市 $T$ とする。
- $X$ は、$S$ $+$ (都市 $T$ から都市 $1$ に向かう途中に通る必要のある道の本数の最小値) である。
- ただし、神殿が存在しないとき $X$ は $-10^{10^{10}}$ である。
幸運なことに彼は、
- 整数 $l$ , $r$ ($1$ $\leq$ $l$ $\leq$ $r$ $\leq$ $K$) を選び、番号 (都市の番号ではないことに注意) が $l$ 以上 $r$ 以下のすべての神殿をビームにより消滅させる
パ研君には最も効率的なビームの放ち方を考えることは難しかったので、あなたに可能な操作により達成できる最大の $X$ を求める事を依頼しました。
しかし、あなたは神殿を消滅させることに良心の呵責を感じたため、$\frac{K(K+1)}{2}+1$ 通りの全ての操作方法について $X$ を求めたあと、この中央値をパ研君に伝えることにしました。
ここで中央値とは、全ての操作方法によって達成できる $X$ のうち、小さい方から $\left\lfloor \frac{\left(\frac{K(K+1)}{2}+1\right)+1}{2}\right\rfloor$ 番目の値のことを指します。
入力
$N\ K$
$C_1\ C_2\ \dots\ C_K$
$D_1\ D_2\ \dots\ D_K$
$A_1\ B_1$
$A_2\ B_2$
$\dots$
$A_{N-1}\ B_{N-1}$
- $2\leq K\leq N\leq 10^5$
- $1\leq C_i\leq N (1\leq i\leq K)$
- $C_i\neq C_j (1\leq i < j\leq K)$
- $-10^9\leq D_i\leq 10^9 (1\leq i\leq K)$
- $1\leq A_i,B_i\leq N (1\leq i\leq N-1)$
- 入力は全て整数。
- 入力で与えられるグラフは木である。
出力
$X$ の中央値を求めてください。 最後に改行してください。
サンプル
サンプル1
入力
3 2 2 3 1 1 1 2 2 3
出力
2
$4$ 通り全てのコストは $-10^{10^{10}}, 2, 3, 3$ となり、中央値は $2$ です。
サンプル2
入力
7 3 4 5 7 1 10 100 1 2 2 3 3 4 3 5 1 6 6 7
出力
101
$7$ 通り全てのコストは $-10^{10^{10}}, 4, 13, 101, 102, 110, 111$ であり、中央値は $101$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。