Codeforces Round 872 (Div. 1) |
---|
Finished |
LuoTianyi is watching the anime Made in Abyss. She finds that making a Cartridge is interesting. To describe the process of making a Cartridge more clearly, she abstracts the original problem and gives you the following problem.
You are given a tree $$$T$$$ consisting of $$$n$$$ vertices. Each vertex has values $$$a_i$$$ and $$$b_i$$$ and each edge has values $$$c_j$$$ and $$$d_j$$$.
Now you are aim to build a tree $$$T'$$$ as follows:
Let $$$A$$$ be the minimum of values $$$a_i$$$ in $$$T'$$$ and $$$C$$$ be the minimum of values $$$c_i$$$ in $$$T'$$$. Let $$$B$$$ be the sum of $$$b_i$$$ in $$$T'$$$ and $$$D$$$ be the sum of values $$$d_i$$$ in $$$T'$$$. Let $$$\min(A, C) \cdot (B + D)$$$ be the cost of $$$T'$$$. You need to find the maximum possible cost of $$$T'$$$.
The first line contains one integer $$$n$$$ ($$$3\le n \le 2\cdot 10^5$$$) — the number of vertices in the tree $$$T$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$a_i$$$ value of the $$$i$$$-th vertex.
The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$b_i$$$ value of the $$$i$$$-th vertex.
Then $$$n-1$$$ lines follow, the $$$j$$$-th of them contains four integers $$$x_j,y_j,c_j,d_j$$$ ($$$1\le x_j,y_j\le n,1\le c_j,d_j\le 2\cdot 10^5$$$) representing the edge $$$(x_j,y_j)$$$ and its values $$$c_j$$$ and $$$d_j$$$ respectively. It's guaranteed that edges form a tree.
Print a single integer — the maximum possible cost of $$$T'$$$.
3 1 2 2 1 1 2 1 2 2 1 1 3 1 2
8
5 2 4 2 1 1 2 4 4 4 4 2 5 3 3 3 5 2 4 4 2 5 5 5 1 1 5
35
6 5 7 10 7 9 4 6 9 7 9 8 5 2 1 5 1 3 2 2 4 4 3 6 3 5 1 7 4 6 5 6 8
216
5 1000 1000 1 1000 1000 1000 1000 1 1000 1000 1 2 1 1 2 3 1000 1000 3 4 1000 1000 3 5 1000 1000
7000000
The tree from the first example is shown in the statement.
The tree from the second example is shown below:
$$$A = 1, B = 18, C = 1, D = 17$$$, so the cost is $$$\min(1,1) \cdot (18 + 17) = 35$$$.
Name |
---|