Дано дерево на 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 до какого-либо листа.
3
2 10 -1
7 -7 5
2 3
2 1
10 50 0
4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3
-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.
Название |
---|