树上纯树

题目描述

有一颗 $n$ 个节点的树（节点从 $1$ 到 $n$ 依次编号），根节点为 $1$。每个节点有两个权值，第 $i$ 个节点的权值为 $a_i,b_i$。

你可以从一个节点跳到它的子树内任意一个节点上。从节点 $x$ 跳到节点 $y$ 一次的花费为 $a_x\times b_y$。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。请分别计算出每个节点到达它子树中叶子节点的费用中的最小值。

注意：就算根节点的度数为 $1$，根节点也不算做叶子节点。另外，不能从一个节点跳到它自己。

输入格式

第一行一个正整数 $n$，表示点数。

第二行和第三行分别输入 $n$ 个整数，表示 $a$ 和 $b$。

接下去 $n-1$ 行，每行两个正整数 $x,y$，描述了树上的一条边，连接 $x,y$。

输出格式

输出一行 $n$ 个整数，第 $i$ 个数表示从 $i$ 号点出发到达某个叶子结点的最小路径总费用。

样例

Input 1

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

Output 1

10 50 0

Input 2

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

Output 2

-300 100 0 0

提示说明

对于前 $0\%$ 的数据，是样例。

对于前 $20\%$ 的数据，保证 $n\le 100$。

对于前 $50\%$ 的数据，保证 $n\le 5000$。

对于另外 $20\%$ 的数据，保证 $a_i$ 全部相等。

对于 $100\%$ 的数据，保证 $n\le 10^5,-10^5 \le a_i,b_i\le 10^5$。