CF932F.Escape Through Leaf

You are given a tree with n nodes (numbered from 1 to n) rooted at node 1. Also, each node has two values associated with it. The values for i-th node are a__i and b__i.

You can jump from a node to any node in its subtree. The cost of one jump from node x to node y is the product of a__x and b__y. The total cost of a path formed by one or more jumps is sum of costs of individual jumps. For every node, calculate the minimum total cost to reach any leaf from that node. Pay attention, that root can never be leaf, even if it has degree 1.

Note that you cannot jump from a node to itself.

给你一棵包含 $n$ 个节点（编号从 $1$ 到 $n$）的树，根节点为节点 $1$。此外，每个节点关联两个值：第 $i$ 个节点的值为 $a_i$ 和 $b_i$。

你可以从一个节点跳转到其子树中的任意节点。从节点 $x$ 跳转到节点 $y$ 的代价为 $a_x \cdot b_y$。由一次或多次跳转构成的一条路径的总代价，等于各次跳转代价之和。对每个节点，请计算从该节点出发到达任意叶节点的最小总代价。注意：即使根节点的度数为 $1$，它也永远不是叶节点。

注意：你不能从一个节点跳转到它自身。

The first line of input contains an integer n (2 ≤ n ≤ 105) — the number of nodes in the tree.

The second line contains n space-separated integers _a_1,  _a_2,  ...,  a__n( - 105  ≤  a__i  ≤  105).

The third line contains n space-separated integers _b_1,  _b_2,  ...,  b__n( - 105  ≤  b__i  ≤  105).

Next n  -  1 lines contains two space-separated integers u__i and v__i (1 ≤ u__i,  v__i ≤  n) describing edge between nodes u__i and v__i in the tree.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 10^5$）——树中节点的数量。

第二行包含 $n$ 个用空格分隔的整数 $a_1,\ a_2,\ \dots,\ a_n$（$-10^5 \leq a_i \leq 10^5$）。

第三行包含 $n$ 个用空格分隔的整数 $b_1,\ b_2,\ \dots,\ b_n$（$-10^5 \leq b_i \leq 10^5$）。

接下来的 $n-1$ 行每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$1 \leq u_i,\ v_i \leq n$），描述树中节点 $u_i$ 与 $v_i$ 之间的一条边。

Output n space-separated integers, i-th of which denotes the minimum cost of a path from node i to reach any leaf.

输出 n 个空格分隔的整数，其中第 i 个整数表示从节点 i 到任意叶节点的路径的最小代价。

In the first example, node 3 is already a leaf, so the cost is 0. For node 2, jump to node 3 with cost _a_2 × _b_3 = 50. For node 1, jump directly to node 3 with cost _a_1 × _b_3 = 10.

In the second example, node 3 and node 4 are leaves, so the cost is 0. For node 2, jump to node 4 with cost _a_2 × _b_4 = 100. For node 1, jump to node 2 with cost _a_1 × _b_2 =  - 400 followed by a jump from 2 to 4 with cost _a_2 × _b_4 = 100.

在第一个例子中，节点 3 已经是叶子节点，因此代价为 0。对于节点 2，跳转到节点 3 的代价为 $a_2 \times b_3 = 50$。对于节点 1，直接跳转到节点 3 的代价为 $a_1 \times b_3 = 10$。

在第二个例子中，节点 3 和节点 4 均为叶子节点，因此代价均为 0。对于节点 2，跳转到节点 4 的代价为 $a_2 \times b_4 = 100$。对于节点 1，先跳转到节点 2，代价为 $a_1 \times b_2 = -400$，再从节点 2 跳转到节点 4，代价为 $a_2 \times b_4 = 100$。