F. Escape Through Leaf

给你一棵包含 #cf_span[n] 个节点的树（节点编号为 #cf_span[1] 到 #cf_span[n]），根节点为 #cf_span[1]。每个节点有两个关联值，第 #cf_span[i] 个节点的值为 #cf_span[ai] 和 #cf_span[bi]。 你可以从一个节点跳到其子树中的任意节点。从节点 #cf_span[x] 跳到节点 #cf_span[y] 的代价为 #cf_span[ax] 与 #cf_span[by] 的乘积。由一次或多次跳跃构成的路径的总代价为各次跳跃代价之和。对于每个节点，计算从该节点到达任意叶子节点的最小总代价。注意，即使根节点的度为 #cf_span[1]，它也不能被视为叶子节点。 你不能从一个节点跳到它自身。 输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]）——树中节点的数量。 第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1,  a2,  ...,  an]（#cf_span[ - 105  ≤  ai  ≤  105]）。 第三行包含 #cf_span[n] 个空格分隔的整数 #cf_span[b1,  b2,  ...,  bn]（#cf_span[ - 105  ≤  bi  ≤  105]）。 接下来的 #cf_span[n  -  1] 行，每行包含两个空格分隔的整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui,  vi ≤  n]），描述树中节点 #cf_span[ui] 与 #cf_span[vi] 之间的边。 请输出 #cf_span[n] 个空格分隔的整数，第 #cf_span[i] 个整数表示从节点 #cf_span[i] 到达任意叶子节点的最小代价。 在第一个示例中，节点 #cf_span[3] 本身已是叶子节点，因此代价为 #cf_span[0]。对于节点 #cf_span[2]，跳到节点 #cf_span[3]，代价为 #cf_span[a2 × b3 = 50]。对于节点 #cf_span[1]，直接跳到节点 #cf_span[3]，代价为 #cf_span[a1 × b3 = 10]。 在第二个示例中，节点 #cf_span[3] 和节点 #cf_span[4] 是叶子节点，因此代价为 #cf_span[0]。对于节点 #cf_span[2]，跳到节点 #cf_span[4]，代价为 #cf_span[a2 × b4 = 100]。对于节点 #cf_span[1]，先跳到节点 #cf_span[2]，代价为 #cf_span[a1 × b2 =  - 400]，再从 #cf_span[2] 跳到 #cf_span[4]，代价为 #cf_span[a2 × b4 = 100]。 ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 105]）——树中节点的数量。第二行包含 #cf_span[n] 个空格分隔的整数 #cf_span[a1,  a2,  ...,  an]（#cf_span[ - 105  ≤  ai  ≤  105]）。第三行包含 #cf_span[n] 个空格分隔的整数 #cf_span[b1,  b2,  ...,  bn]（#cf_span[ - 105  ≤  bi  ≤  105]）。接下来的 #cf_span[n  -  1] 行，每行包含两个空格分隔的整数 #cf_span[ui] 和 #cf_span[vi]（#cf_span[1 ≤ ui,  vi ≤  n]），描述树中节点 #cf_span[ui] 与 #cf_span[vi] 之间的边。 ## Output 请输出 #cf_span[n] 个空格分隔的整数，第 #cf_span[i] 个整数表示从节点 #cf_span[i] 到达任意叶子节点的最小代价。 [samples] ## Note 在第一个示例中，节点 #cf_span[3] 本身已是叶子节点，因此代价为 #cf_span[0]。对于节点 #cf_span[2]，跳到节点 #cf_span[3]，代价为 #cf_span[a2 × b3 = 50]。对于节点 #cf_span[1]，直接跳到节点 #cf_span[3]，代价为 #cf_span[a1 × b3 = 10]。 在第二个示例中，节点 #cf_span[3] 和节点 #cf_span[4] 是叶子节点，因此代价为 #cf_span[0]。对于节点 #cf_span[2]，跳到节点 #cf_span[4]，代价为 #cf_span[a2 × b4 = 100]。对于节点 #cf_span[1]，先跳到节点 #cf_span[2]，代价为 #cf_span[a1 × b2 =  - 400]，再从 #cf_span[2] 跳到 #cf_span[4]，代价为 #cf_span[a2 × b4 = 100]。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of nodes in a tree rooted at node $ 1 $. For each node $ i \in \{1, \dots, n\} $, let $ a_i, b_i \in \mathbb{Z} $ be associated values. Let $ T = (V, E) $ be the tree with $ V = \{1, \dots, n\} $, and edges defined by $ n-1 $ pairs $ (u_i, v_i) $. Let $ \text{children}(i) $ denote the set of direct children of node $ i $. Let $ \text{leaves} \subseteq V $ be the set of leaf nodes (nodes with no children). **Constraints** 1. $ 2 \leq n \leq 10^5 $ 2. $ -10^5 \leq a_i, b_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $ 3. The tree is rooted at node $ 1 $, and node $ 1 $ is not a leaf. 4. A jump is allowed from node $ x $ to node $ y $ if $ y $ is in the subtree of $ x $ and $ y \neq x $. 5. Cost of jump from $ x $ to $ y $: $ a_x \cdot b_y $. 6. Total cost of a path: sum of costs of individual jumps. **Objective** For each node $ i \in \{1, \dots, n\} $, compute $ \text{dp}[i] $, the minimum total cost to reach any leaf from node $ i $, where: - If $ i $ is a leaf, $ \text{dp}[i] = 0 $. - Otherwise, $$ \text{dp}[i] = \min_{\substack{y \in \text{subtree}(i) \\ y \neq i}} \left( a_i \cdot b_y + \text{dp}[y] \right) $$ Equivalently, by structural recursion over the tree: $$ \text{dp}[i] = \min \left( \min_{j \in \text{children}(i)} \left( a_i \cdot b_j + \text{dp}[j] \right), \min_{\substack{j \in \text{children}(i) \\ y \in \text{subtree}(j)}} \left( a_i \cdot b_y + \text{dp}[y] \right) \right) $$ But since any descendant $ y $ can be reached via a single jump, it suffices to consider: $$ \text{dp}[i] = \min_{y \in \text{subtree}(i) \setminus \{i\}} \left( a_i \cdot b_y + \text{dp}[y] \right) $$ with base case $ \text{dp}[i] = 0 $ for all leaves $ i $. **Output** $ \text{dp}[1], \text{dp}[2], \dots, \text{dp}[n] $