P4629 [SHOI2015] Fusion Reactor

The inventor SHTSC, who once created the parts assembler, has now revealed his new invention: a fusion reactor—a mysterious device that can produce a large amount of clean energy. As is well known, there are two difficulties in harnessing energy from nuclear fusion: one is controlling the intensity of the fusion reaction, and the other is activating the fusion reaction using as little energy as possible. SHTSC has perfectly solved the first problem. A fusion reactor consists of several interconnected fusion blocks. To ensure controllability, SHTSC guarantees that any two fusion blocks can reach each other via links, and no fusion block can return to itself without repeating an edge. In other words, the links form a tree. However, the second problem is not fully solved. In his design, each fusion block requires a certain initial energy $d_i$ to be activated. Nevertheless, SHTSC does not need to activate all blocks manually, because once a fusion block is activated, it sends $c_i$ units of energy to all directly connected fusion blocks that have not yet been activated. In this way, fusion blocks activated later can be activated with lower initial energy, or even without any additional external energy, thereby reducing the total activation energy. Given a fusion reactor, find the minimum amount of energy required to activate all fusion blocks.

The first line contains an integer $n$, indicating that there are $n$ fusion blocks, numbered $1$ to $n$. The second line contains $n$ integers, representing $d_i$ in order. The third line contains $n$ integers, representing $c_i$ in order. Each of the following $n - 1$ lines contains two integers $u, v$, indicating that fusion blocks $u$ and $v$ are connected.

Output a single integer on one line, indicating the minimum number of energy units required to activate all fusion blocks.

| Case # | $\max\{c_i\}$ | $n$ | Additional constraints | |:---:|:---:|:---:|:---:| | 1 | $= 1$ | $\leq 10$ | $c_i = 1$ | | 2 | $= 1$ | $\leq 100$ | $c_i = 1$ | | 3 | $= 1$ | $\leq 200$ | $c_i = 1$ | | 4 | $= 0$ | $\leq 10$ | - | | 5 | $= 1$ | $\leq 200$ | $c_i = 1$ | | 6 | $= 1$ | $\leq 200$ | - | | 7 | $= 1$ | $\leq 100000$ | $c_i = 1$ | | 8 | $= 0$ | $\leq 100000$ | - | | 9 | $= 1$ | $\leq 100000$ | - | | 10 | $= 1$ | $\leq 100000$ | - | | 11 | $\leq 5$ | $\leq 20$ | - | | 12 | $\leq 5$ | $\leq 20$ | $c_i$ are all equal | | 13 | $\leq 5$ | $\leq 200$ | - | | 14 | $\leq 5$ | $\leq 200$ | $c_i$ are all equal | | 15 | $\leq 5$ | $\leq 200$ | - | | 16 | $\leq 5$ | $\leq 200$ | - | | 17 | $\leq 5$ | $\leq 2000$ | $c_i$ are all equal | | 18 | $\leq 5$ | $\leq 2000$ | - | | 19 | $\leq 5$ | $\leq 2000$ | - | | 20 | $\leq 5$ | $\leq 2000$ | - | For all testdata, it is guaranteed that $1 \le d_i, \sum d_i \le 10^9$. Translated by ChatGPT 5