← 返回题目列表

Codeforces · 932/F

F. 透过树叶逃走

中文机器翻译题面 查看原题

给定一棵树,其中有 n 个节点(编号从 1 到 n),根节点为节点 1。此外,每个节点都有两个与其关联的值。第 i 个节点的值为 ai 和 bi。

您可以从一个节点跳转到其子树中的任何节点。从节点 x 到节点 y 的一次跳转的成本是 ax 和 by 的乘积。由一次或多次跳跃形成的路径的总成本是各个跳跃的成本之和。对于每个节点,计算从该节点到达任何叶子的最小总成本。请注意,根永远不可能是叶,即使它的度数为 1。

请注意,您不能从一个节点跳转到其自身。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 105) — 树中的节点数。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an( - 105 ≤ ai ≤ 105)。

第三行包含 n 个空格分隔的整数 b1, b2, ..., bn( - 105 ≤ bi ≤ 105)。

接下来的 n - 1 行包含两个空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n) 描述树中节点 ui 和 vi 之间的边。

输出

输出 n 个空格分隔的整数,其中第 i 个表示从节点 i 到达任何叶子的路径的最小成本。

示例

输入 #1

3
2 10 -1
7 -7 5
2 3
2 1

输出 #1

10 50 0

输入 #2

4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3

输出 #2

-300 100 0 0

注意

在第一个示例中,节点 3 已经是叶子,因此成本为 0。对于节点 2,跳转到节点 3,成本为 a2 × b3 = 50。对于节点 1,直接跳转到节点 3,成本为 a1 × b3 = 10。

在第二个示例中,节点 3 和节点 4 是叶子,因此成本为 0。对于节点 2,跳转到节点 4,成本为 a2 × b4 = 100。对于节点 1,跳转到节点 2,成本为 a1 × b2 = - 400,然后从 2 跳转到节点 4,成本为 a2 × b4 = 100。