← 返回题目列表

Codeforces · 1394/D

D. 波波纽与江湖

中文机器翻译题面 查看原题

波博尼自从建好江湖后,每天都在这些山上练功夫。

Boboniu 为他的 $$$n$$$ 山脉设计了一张地图。他使用 $$$n-1$$$ 道路连接所有 $$$n$$$ 山脉。每对山都通过道路连接起来。

对于第 $$$i$$$ 座山,Boboniu 估计在其顶部练习功夫的疲劳程度为 $$$t_i$$$。他还估计每座山的高度为$$$h_i$$$。

路径是一系列山脉 $$$M$$$,因此对于每个 $$$i$$$ ($$$1 \le i < |M|$$$),$$$M_i$$$ 和 $$$M_{i+1}$$$ 之间存在一条道路。如果对于每个 $$$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}$$$。

他要求你找到最小的总疲劳度。作为对你工作的奖励,你将成为他江湖的守护者。

输入

第一行包含一个整数 $$$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$$$),表示道路的端点。保证所有的山都有路相连。

输出

打印一个整数:所有挑战的疲劳度之和最小。

示例

输入 #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

注意

对于第一个示例:

图中,点越亮,代表的山越高。最好的部门之一是:

- 挑战 $$$1$$$: $$$3 \to 1 \to 2$$$
- 挑战 $$$2$$$: $$$5 \to 2 \to 4$$$

Boboniu 的总疲劳度为 $$$(30 + 40 + 10) + (20 + 10 + 50) = 160$$$。可以证明这是最小的总疲劳度。