問題一覧 > 通常問題

No.1221 Tree *= 3

レベル : / AI推定難易度 : 1425 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 163
作問者 : anagohirame / テスター : Kiri8128
お気に入りにしたユーザー ProblemId : 4639 / 自分の提出
問題文最終更新日: 2020-08-31 02:15:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 264 (順位表) の他の問題:

Problem Statement

There is a tree with $N$ vertices, and the $i$-th edge connects vertex $u_i$ and vertex $v_i$.
You may delete 0 or more vertices from this tree. There are $2^N$ ways to choose the vertices to delete, and for each choice, the score is defined according to the following rules.

  • Initialize the score to $0$.
  • For every integer $i$ between $1$ and $N$, inclusive, do the following.
    • If vertex $i$ has been deleted, add $a_i$ to the score.
    • If vertex $i$ remains undeleted, let $d_i$ be the number of undeleted vertices adjacent to vertex $i$, and add $d_i\times b_i$ to the score.
What is the maximum among the $2^N$ scores calculated in this way?

Input

$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}$

  • All input values are integers.
  • $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$
  • The given graph is a tree.

Output

Output the maximum obtainable score on one line.

Sample

Sample 1
Input
4
2 1 4 8
5 -1 0 1
1 2
1 3
1 4
Output
17

Delete only vertex 4, and keep vertices 1, 2, 3. In this case,

  • For vertex 1: vertex 1 remains and $d_1=2$ (vertices 2, 3), so add $2\times b_1=10$ to the score.
  • For vertex 2: vertex 2 remains and $d_2=1$ (vertex 1), so add $1\times b_2=-1$ to the score.
  • For vertex 3: vertex 3 remains and $d_3=1$ (vertex 1), so add $1\times b_3=0$ to the score.
  • For vertex 4: vertex 4 has been deleted, so add $a_4=8$ to the score.
Therefore, the score of this way of deleting is 17. No other way of deleting vertices can exceed this score, so this is the maximum.

Sample 2
Input
2
-40 -20
-10 -30
2 1
Output
-20

It is optimal to keep vertex 1 and delete vertex 2. The maximum may be negative.

Sample 3
Input
1
-1000000000
1000000000
Output
0

Sample 4
Input
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
Output
3621999149

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