题目背景

题目来源：https://hsin.hr/hio2023/。翻译来自 文心一言。如果有更好的翻译请在讨论区提供。

题目描述

Borova Suma，位于河流对岸，一小时前还被五月的阳光照亮，现在却变得朦胧、模糊并散开。只剩下一棵神奇的大树，一棵有 $N$ 个节点的树……

Ivan 从 119 号房间观察着这棵树，它坚固地扎根在标有数字 $1$ 的节点上。之后，他更近距离地观察了树，发现每个节点上都有一个数字 $a$。突然，他脑海中浮现出了 $k$-好子树的定义。一个子树是 $k$-好的，如果对于连接节点 $(u,v)$ 的每一条边（其中 $u$ 是 $v$ 的父节点），都有 $a_v = (a_u + 1) \bmod k$ 成立，并且对于子树内的每个节点 $v$，都满足 $a_v < k$。对于每个数字 $k$，都存在一个自然的 $k$-好子树的不稳定性，记作 $f(k)$。

当他再次回过神来时，他发现自己站在树前，右手拿着一把神奇的斧头。Ivan 决定砍掉一些树枝，并在移除某些边后得到的每个子树中，选择一个数字 $k$，使得该子树是 $k$-好的。对于选择哪些边进行砍伐以及为每个得到的子树选择的 $k$ 值，Ivan 决定称之为“砍伐”。我们将砍伐的不稳定性定义为所有得到的 $k$-好子树的 $f(k_i)$ 之和。请帮助 Ivan 确定砍伐的最小可能不稳定性。

输入格式

第一行是一个自然数 $N$，表示树中节点的数量。

第二行包含 $N$ 个数字，其中第 $i$ 个数字表示节点 $i$ 的权值 $a$（$0 \leq a \leq N - 1$）。

第三行包含 $N$ 个数字，其中第 $k$ 个数字表示函数 $f(k)$ 的值（$1 \leq f(k) \leq 10^9$）。

接下来的 $N-1$ 行描述了树的结构，第 $i$ 行包含两个数字 $u$ 和 $v$（$1 \leq u,v \leq N, u \neq v$），表示节点 $u$ 和节点 $v$ 之间存在一条边。

输出格式

在单独的一行中输出可能的最小“锯割不稳定性”。

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

提示

【样例解释】

左图为样例 1，右图为样例 2。

【数据范围】

在所有子任务中，都满足 $1 ≤ N ≤ 3\times 10^5$ 的条件。

• 子任务 1（12 分）：$N \leq 5 000$，树是一条链，且节点 $1$ 是链的一个端点。
• 子任务 2（20 分）：$N \leq 300 000$，树是一条链，且节点 $1$ 是链的一个端点。
• 子任务 3（7 分）：$N \leq 20$；
• 子任务 4（22 分）：$N \leq 5000$；
• 子任务 5（39 分）：没有其他额外限制。