Background

Source: https://hsin.hr/hio2023/。

Problem Description

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!

Input Format

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

Output Format

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

7
2 3 0 3 2 0 0
6 8 2 9 9 9 9
1 2
2 3
1 4
4 5
5 6
5 7

11

7
2 3 0 3 2 0 0
6 8 2 9 9 9 1
1 2
2 3
1 4
4 5
5 6
5 7

4

Hint

[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