Boboniu and Jianghu
Contest: Codeforces Round 664 (Div. 1)
Difficulty rating: 2800
Tags: dp, greedy, sortings, trees

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.

Input format:
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.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
40 10 30 50 20
2 3 2 3 1
1 2
1 3
2 4
2 5

Example output:
160

Example input:
5
1000000 1 1 1 1
1000000 1 1 1 1
1 2
1 3
1 4
1 5

Example output:
4000004

Editorial:
Generally speaking, you're asked to use some simple directed paths (challenges) to cover the original tree and minimize the total cost (tiredness). Those edges with $$$h_u \neq h_v$$$ are already oriented, and for the other ones, we need to determine their directions.
At first, let's consider the case where each edge has already been oriented (or, for all edges $$$(u, v)$$$, $$$h_u \neq h_v$$$ holds).
We use $$$P(u, v)$$$ to denote the directed path from $$$u$$$ to $$$v$$$.
In the beginning, for each edge $$$u \to v$$$, let's set up $$$P(u, v)$$$ to cover it. Thus the total cost of it is obviously $$$\sum_{i = 1}^{n} \text{deg}(i) \cdot t_i$$$, where $$$\text{deg}_i$$$ denotes the degree of vertex $$$i$$$.
We can choose two challenge $$$P(x, y)$$$ and $$$P(y, z)$$$ ($$$y$$$ should be on $$$P(x, z)$$$) and merge them together to get a single challenge $$$P(x, z)$$$. This operation will reduce the total tiredness by $$$t_y$$$. Thus we try to do such operation to maximize the total reduction.
For vertex $$$i$$$, suppose that there are $$$\text{in}_i$$$ challenges end at $$$i$$$ and $$$\text{out}_i$$$ challenges start from $$$i$$$. Thus the total reduction is $$$\sum_{i = 1}^{n} \min(\text{in}_i, \text{out}_i) \cdot t_i$$$.
Now, let's try to solve the original problem.
For the directed edges, we calculate $$$\text{in}'_i$$$ and $$$\text{out}'_i$$$ for every vertex $$$i$$$, and we can delete them from the tree. For the undirected edges, they form several small trees (a forest).
Let's choose an arbitrary root for each tree and do a DP on it. Let $$$p_u$$$ be the father of $$$u$$$. For a non-root vertex $$$u$$$ and its subtree, $$$f_u$$$ denotes the maximum reduction when we orient $$$p_u \to u$$$ (down), and $$$g_u$$$ denotes the maximum reduction when we orient $$$u \to p_u$$$ (up).
Take $$$f_u$$$ for example. To calculate it, we should know the in degree and out degree of $$$u$$$ (after directing the edges).
Suppose that $$$u$$$ has $$$c$$$ children. If $$$x$$$ of them are oriented end at $$$u$$$ (up) and $$$(s - x)$$$ of them are oriented start from $$$u$$$ (down), the reduction of $$$u$$$ is $$$\min(\text{in}'_u + 1 + x, \text{out}'_u + (s - x)) \cdot t_u$$$ ($$$+ 1$$$ because $$$p_u \to u$$$).
Now the question changes to: You are given $$$c$$$ vertices $$$v_1, v_2,\ldots, v_c$$$, choose $$$x$$$ of them forming a set $$$A$$$. Maximize $$$\sum_{v \in A} g_v + \sum_{v \notin A} f_v$$$. Calculate the maximum value for all $$$0 \le x \le c$$$. Actually, you can sort $$$[v_1, v_2, \cdots, v_c]$$$ by $$$(f_v - g_v)$$$ and calculate the prefix sum $$$s_i$$$. The answer for $$$x = i$$$ is simply $$$s_i + \sum_v g_v$$$.
The calculation for $$$g_u$$$ and the root is similar. The total time complexity is $$$O(n \log n)$$$.