問題一覧 > 通常問題

No.1215 都市消滅ビーム

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 8
作問者 : ThistleThistle / テスター : autumn-eelautumn-eel
1 ProblemId : 4896 / 出題時の順位表
問題文最終更新日: 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}}$ である。

ある日、この国に住むパ研君は神のために $X$ を出来るだけ大きくしようと思い立ちました。
幸運なことに彼は、

  • 整数 $l$ , $r$ ($1$ $\leq$ $l$ $\leq$ $r$ $\leq$ $K$) を選び、番号 (都市の番号ではないことに注意) が $l$ 以上 $r$ 以下のすべての神殿をビームにより消滅させる
という操作を $1$ 回以下行うことができます。

パ研君には最も効率的なビームの放ち方を考えることは難しかったので、あなたに可能な操作により達成できる最大の $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もしくは右上の雲マークをクリックしてアカウントを作成してください。