No.1221 Tree *= 3
タグ : / 解いたユーザー数 163
作問者 :
anagohirame
/ テスター :
Kiri8128
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.
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.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。