問題一覧 > 通常問題

No.1221 木 *= 3

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 123
作問者 : anagohirameanagohirame / テスター : Kiri8128Kiri8128
10 ProblemId : 4639 / 出題時の順位表
問題文最終更新日: 2020-08-31 02:15:24

問題文

$N$ 頂点の木があり, $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ をつないでいます。
あなたは,この木から0個以上の頂点を消すことができます。消す頂点の選び方は $2^N$ 通り存在しますが,それぞれの選び方について,スコアが以下の規則に従って定義されます。

  • スコアを $0$ で初期化する。
  • $1$ 以上 $N$ 以下のすべての整数 $i$ について,以下を行う。
    • 頂点 $i$ が消されている場合,スコアに $a_i$ を加算する。
    • 頂点 $i$ が消されずに残っている場合,頂点 $i$ に隣接しかつ消されずに残っている頂点の数を $d_i$ としたとき,スコアに $d_i\times b_i$ を加算する。
このようにして計算される $2^N$ 通りのスコアのうち,最大値はいくつでしょうか?

入力

$N$
$a_1\ a_2\ \cdots\ a_N$
$b_1\ b_2\ \cdots\ b_N$
$u_1\ v_1$
$\vdots$
$u_{N-1}\ v_{N-1}$

  • 入力はすべて整数
  • $1\le N\le 10^5$
  • $-10^9 \le a_i \le 10^9$
  • $-10^9 \le b_i \le 10^9$
  • $1\le u_i, v_i\le N$
  • 与えられるグラフは木である

出力

得られるスコアの最大値を1行に出力してください。

サンプル

サンプル1
入力
4
2 1 4 8
5 -1 0 1
1 2
1 3
1 4
出力
17

頂点4のみを消し,頂点1, 2, 3を残します。このとき,

  • 頂点1について:頂点1は残っており,$d_1=2$(頂点2, 3)なので,スコアに $2\times b_1=10$ を加算します。
  • 頂点2について:頂点2は残っており,$d_2=1$(頂点1)なので,スコアに $1\times b_2=-1$ を加算します。
  • 頂点3について:頂点3は残っており,$d_3=1$(頂点1)なので,スコアに $1\times b_3=0$ を加算します。
  • 頂点4について:頂点4は消されたので,スコアに $a_4=8$ を加算します。
より,この消し方のスコアは17です。他の頂点の消し方でこのスコアを超えることはできず,これが最大値です。

サンプル2
入力
2
-40 -20
-10 -30
2 1
出力
-20

頂点1を残し,頂点2を消すのが最適です。最大値が負となることもあります。

サンプル3
入力
1
-1000000000
1000000000
出力
0

サンプル4
入力
7
-521286975 241394095 679500630 908939842 -663879330 -918836774 -200080451
-521243563 425878585 50490545 924277174 963020278 437158704 866091708
1 2
1 3
2 4
2 5
3 6
3 7
出力
3621999149

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。