P10754 [COI 2023] Nestabilnost

Source: 。

The pine forest across the river, which was still bathed in May sunshine an hour ago, has now become blurry, hazy, and faded away. Only one huge tree remains, a tree with $N$ nodes... Ivan is in room 119, observing this tree, which is firmly rooted at node $1$. After looking at the tree more carefully, he notices that each node $i$ has a number $a_i$ on it. Suddenly, the definition of a **$k$-good subtree** ("k-dobrog podstabla") flashes through his mind. If for every edge connecting nodes $(u, v)$ in a subtree (where $u$ is the parent of $v$), we have $a_v = (a_u + 1) \pmod k$, and for every node $v$ in that subtree, we have $a_v < k$, then this subtree is **$k$-good**. For each number $k$, there is a natural instability of a **$k$-good** subtree, denoted by $f(k)$. When he comes back to his senses, he notices a raft floating in front of the tree, and in his right hand he is holding a magic saw. Ivan decides to saw off some branches (edges). For each connected component (subtree) obtained by removing the sawed edges, he will choose a number $k_i$ such that this component is **$k_i$-good**. Ivan decides to call such a set of choices—choosing a set of edges to cut, and choosing for each resulting subtree a valid $k_i$ (so that the subtree is **$k_i$-good**)—a **cutting ("rezanjem")**. The **instability ("Nestabilnost")** of a **cutting** is defined as the sum of $f(k_i)$ over all resulting subtrees. Please help Ivan determine the minimum possible **instability** of a **cutting**!

The first line contains a positive integer $N$, the number of nodes in the tree. The second line contains $N$ integers, where the $i$-th number is $a_i$ ($0 \le a_i \le N - 1$). The third line contains $N$ integers, where the $k$-th number is $f(k)$ ($1 \le f(k) \le 10^9$). The next $N - 1$ lines describe the structure of the tree. The $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le N, u_i \ne v_i$), indicating that there is an edge between nodes $u_i$ and $v_i$.

In the only line, output the minimum possible **instability** of a **cutting**.

**[Sample Explanation]**  The left picture is sample 1, and the right picture is sample 2. **[Constraints]** In all subtasks, $1 \le N \le 3\times 10^5$. - Subtask 1 (12 points): $N \leq 5 000$, the tree is a chain, and node $1$ is an endpoint of the chain. - Subtask 2 (20 points): $N \leq 300 000$, the tree is a chain, and node $1$ is an endpoint of the chain. - Subtask 3 (7 points): $N \leq 20$. - Subtask 4 (22 points): $N \leq 5000$. - Subtask 5 (39 points): No additional constraints. Translated by ChatGPT 5