[AdditionalFile5490.zip](file://AdditionalFile5490.zip?type=additional_file)

#5490. 「COI 2023」Nestabilnost

标签: 传统 | 时间限制: 1500 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2023 T2「Nestabilnost」

河对岸的树林，一小时前还在五月的阳光下闪耀，现在已经变得昏暗、模糊并消融了。只剩下一棵巨大的树，一棵有 $N$ 个节点的树……

伊凡在他编号为 $119$ 的房间里凝视着这棵树。它的根牢牢地扎在编号为 $1$ 的节点上。仔细观察后，他注意到每个节点上都写着一个对应的数字 $a_{i}$。突然，一个念头闪现在他的脑海中——关于 $k$-优子树的定义。

首先，给定树的子树被定义为树节点的任意连通子集。对于一个整数 $k$ $(1 \leq k \leq N)$，如果一个子树满足以下条件，则称其为 $k$-优的：对于子树中每一条形如 $(u, v)$ 的边（其中 $u$ 是 $v$ 的父节点），都满足 $a_{v}=\left(a_{u}+1\right) \bmod k$；并且，对于子树中的每个节点 $v$，都必须满足 $a_{v}<k$。此外，对于每个 $k=1,2, \ldots, N$，都给定了一个数 $f(k)$，代表 $k$-优子树的自然不稳定性。

当他再次转身时，他发现自己实际上正右手拿着一把魔法锯子漂浮在树旁。伊凡决定砍掉树的一些枝干，然后为切割后剩下的每一棵子树选择一个整数 $k_{i}$，使得相应的子树都是 $k_{i}$-优的。一次切割包括选择要砍掉的边，以及选择相应的数字 $k_{i}$ 以满足上述条件。一次切割的不稳定性定义为该切割产生的所有子树的 $f\left(k_{i}\right)$ 之和。请帮助伊凡确定一次切割可能达到的最小不稳定性。

输入格式

第一行包含一个正整数 $N$，表示树中的节点数。

第二行包含 $N$ 个整数，其中第 $i$ 个是 $a_{i}$ $(0 \leq a_{i} \leq N-1)$。

第三行包含 $N$ 个整数，其中第 $k$ 个是 $f(k)$ $(1 \leq f(k) \leq 10^{9})$。

接下来的 $N-1$ 行描述了这棵树。第 $i$ 行包含数字 $u_{i}$ 和 $v_{i}$ $(1 \leq u_{i}, v_{i} \leq N, u_{i} \neq v_{i})$，表示节点 $u_{i}$ 和 $v_{i}$ 之间有一条边。

输出格式

在唯一的一行中输出一次切割可能达到的最小不稳定性。

样例 1

输入

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

样例一的最优切割如下：

样例 2

输入

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

样例二的最优切割如下：

数据范围与提示

对于所有输入数据，满足 $1 \leq N \leq 300000$。

详细子任务附加限制及分值如下表所示：