D. Boboniu и Jianghu
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После того как Boboniu закончил строительство своего Jianghu, он занимался кунг-фу на этих горах каждый день.

Boboniu разработал карту для своих $$$n$$$ гор. Он использовал $$$n-1$$$ дорогу чтобы соединить все $$$n$$$ гор. Все горы связны с помощью дорог.

Для $$$i$$$-й горы, Boboniu оценил скучность кунг-фу на ней как $$$t_i$$$. Он также оценил высоту каждой горы как $$$h_i$$$.

Путь это такая последовательность гор $$$M$$$, что для всех $$$i$$$ ($$$1 \le i < |M|$$$), существует дорога между $$$M_i$$$ и $$$M_{i+1}$$$. Boboniu считает путь испытанием если для всех $$$i$$$ ($$$1\le i<|M|$$$), $$$h_{M_i}\le h_{M_{i+1}}$$$.

Boboniu хочет разделить все $$$n-1$$$ дорог на несколько испытаний. Обратите внимание, что каждая дорога должна встречаться ровно в одном испытании, но гора может встречаться в нескольких испытаниях.

Boboniu хочет минимизировать суммарную скучность всех испытаний. Скучность испытания $$$M$$$ это сумма скучностей всех гор в ней, т.е. $$$\sum_{i=1}^{|M|}t_{M_i}$$$.

Он попросил вас найти минимальную возможную суммарную скучность всех испытаний. В награду за вашу работу, вы станете охранником в его Jianghu.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), обозначающее число гор.

Во второй строке записано $$$n$$$ целых чисел $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le 10^6$$$), обозначающих скучность исполнения кунг-фу для Boboniu на каждой из гор.

В третьей строке записаны $$$n$$$ целых чисел $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^6$$$), описывающих высоты всех гор.

Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i$$$), обозначающих концы дороги. Гарантируется, что все горы связны по дорогам.

Выходные данные

Выведите одно целое число: минимальную возможную суммарную скучность всех испытаний.

Примеры
Входные данные
5
40 10 30 50 20
2 3 2 3 1
1 2
1 3
2 4
2 5
Выходные данные
160
Входные данные
5
1000000 1 1 1 1
1000000 1 1 1 1
1 2
1 3
1 4
1 5
Выходные данные
4000004
Входные данные
10
510916 760492 684704 32545 484888 933975 116895 77095 127679 989957
402815 705067 705067 705067 623759 103335 749243 138306 138306 844737
1 2
3 2
4 3
1 5
6 4
6 7
8 7
8 9
9 10
Выходные данные
6390572
Примечание

В первом примере:

На картинке, чем светлее точка, тем выше гора, которую она представляет. Одно из лучших разделений это:

  • Испытание $$$1$$$: $$$3 \to 1 \to 2$$$
  • Испытание $$$2$$$: $$$5 \to 2 \to 4$$$

Суммарно скучность для Boboniu равна $$$(30 + 40 + 10) + (20 + 10 + 50) = 160$$$. Можно показать, что это является минимальной возможной скучностью.