CF932F Escape Through Leaf

题目描述

给定一棵有 $n$ 个节点的树（节点编号为 $1$ 到 $n$），以节点 $1$ 为根。每个节点都有两个关联值，分别为 $a_i$ 和 $b_i$。

你可以从某个节点跳到其子树中的任意节点。从节点 $x$ 跳到节点 $y$ 的花费为 $a_x \times b_y$。由一次或多次跳跃组成的路径的总花费为各次跳跃花费之和。对于每个节点，计算从该节点到达任意叶子节点的最小总花费。注意，根节点永远不会被视为叶子节点，即使它的度数为 $1$。

注意，不能从一个节点跳到自身。

输入格式

第一行输入一个整数 $n$（$2 \leq n \leq 10^5$），表示树的节点数。

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

第三行输入 $n$ 个用空格分隔的整数 $b_1,b_2,\ldots,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$ 之间有一条边。

输出格式

输出 $n$ 个用空格分隔的整数，第 $i$ 个整数表示从节点 $i$ 到达任意叶子节点的最小花费。

输入输出样例 #1

输入 #1

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

输出 #1

10 50 0 

输入输出样例 #2

输入 #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$ 的花费为 $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$。

由 ChatGPT 4.1 翻译