Boboniu and Jianghu

题意翻译

## 题目描述 有一棵 $n$ 个点的树（$1\le n\le 2\times10^5$），第 $i$ 个点有参数 $a_i,b_i$。（$1\le a_i,b_i\le10^6$） 现在要求把这棵树剖分成若干条链（链包括端点），使每条边恰好出现在一条链中，且要求链上的点的 $b_i$ **单调不降或单调不增**。一条链的权值定义为链上所有点的 $a_i$ 之和。 求在所有剖分方案中，链的总权值最小为多少。 ## 输入 第一行为 $n$； 第二行为 $n$ 个整数 $a_1,a_2\dots,a_n$； 第三行为 $n$ 个整数 $b_1,b_2\dots,b_n$； 接下来 $n-1$ 行每行一条边，表示这棵树。 ## 输出 一行一个整数表示答案。

题目描述

Since Boboniu finished building his Jianghu, he has been doing Kungfu on these mountains every day. Boboniu designs a map for his $ n $ mountains. He uses $ n-1 $ roads to connect all $ n $ mountains. Every pair of mountains is connected via roads. For the $ i $ -th mountain, Boboniu estimated the tiredness of doing Kungfu on the top of it as $ t_i $ . He also estimated the height of each mountain as $ h_i $ . A path is a sequence of mountains $ M $ such that for each $ i $ ( $ 1 \le i < |M| $ ), there exists a road between $ M_i $ and $ M_{i+1} $ . Boboniu would regard the path as a challenge if for each $ i $ ( $ 1\le i<|M| $ ), $ h_{M_i}\le h_{M_{i+1}} $ . Boboniu wants to divide all $ n-1 $ roads into several challenges. Note that each road must appear in exactly one challenge, but a mountain may appear in several challenges. Boboniu wants to minimize the total tiredness to do all the challenges. The tiredness of a challenge $ M $ is the sum of tiredness of all mountains in it, i.e. $ \sum_{i=1}^{|M|}t_{M_i} $ . He asked you to find the minimum total tiredness. As a reward for your work, you'll become a guardian in his Jianghu.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ), denoting the number of the mountains. The second line contains $ n $ integers $ t_1, t_2, \ldots, t_n $ ( $ 1 \le t_i \le 10^6 $ ), denoting the tiredness for Boboniu to do Kungfu on each mountain. The third line contains $ n $ integers $ h_1, h_2, \ldots, h_n $ ( $ 1 \le h_i \le 10^6 $ ), denoting the height of each mountain. Each of the following $ n - 1 $ lines contains two integers $ u_i $ , $ v_i $ ( $ 1 \le u_i, v_i \le n, u_i \neq v_i $ ), denoting the ends of the road. It's guaranteed that all mountains are connected via roads.

输出格式

Print one integer: the smallest sum of tiredness of all challenges.

输入输出样例

输入样例 #1

5
40 10 30 50 20
2 3 2 3 1
1 2
1 3
2 4
2 5

输出样例 #1

160

输入样例 #2

5
1000000 1 1 1 1
1000000 1 1 1 1
1 2
1 3
1 4
1 5

输出样例 #2

4000004

输入样例 #3

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

输出样例 #3

6390572

说明

For the first example: In the picture, the lighter a point is, the higher the mountain it represents. One of the best divisions is: - Challenge $ 1 $ : $ 3 \to 1 \to 2 $ - Challenge $ 2 $ : $ 5 \to 2 \to 4 $ The total tiredness of Boboniu is $ (30 + 40 + 10) + (20 + 10 + 50) = 160 $ . It can be shown that this is the minimum total tiredness.