给定一棵树,其中有 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。