洛天依正在看动漫《深渊制造》。她发现制作墨盒很有趣。为了更清楚地描述制作墨盒的过程,她抽象了原始问题并给出了以下问题。
给你一棵树 $$$T$$$,由 $$$n$$$ 个顶点组成。每个顶点都有值 $$$a_i$$$ 和 $$$b_i$$$,每条边都有值 $$$c_j$$$ 和 $$$d_j$$$。
现在您的目标是构建一棵树$$$T'$$$,如下所示:
- 首先,从$$$T$$$中选择$$$p$$$顶点($$$p$$$是你自己选择的数字)作为$$$T'$$$的顶点集$$$S'$$$。
- 接下来,从 $$$T$$$ 中逐条选择 $$$p-1$$$ 边(不能多次选择一条边)。
- 可能你选择了第$$$j$$$条边连接顶点$$$x_j$$$和$$$y_j$$$,其值为$$$(c_j,d_j)$$$,那么你可以在$$$S'$$$中选择两个满足这条边的顶点$$$u$$$和$$$v$$$ $$$(x_j,y_j)$$$ 包含在 $$$T$$$ 中从 $$$u$$$ 到 $$$v$$$ 的简单路径中,并通过值为 $$$(c_j,d_j)$$$ 的边链接 $$$T'$$$ 中的 $$$u$$$ 和 $$$v$$$($$$u$$$ 和 $$$v$$$ 之前不应包含在一个连通分量中)在$$$T'$$$)。
具有三个顶点的树,$$$\min(A,C)=1,B+D=7$$$,成本为$$$7$$$。
选定顶点 $$$2$$$ 和 $$$3$$$ 作为 $$$S'$$$,使用边 $$$(1,2)$$$ 和 $$$c_j = 2$$$ 和 $$$d_j = 1$$$ 来链接这些顶点,现在 $$$\min(A,C)=2,B+D=4$$$,成本为$$$8$$$。
设 $$$A$$$ 为 $$$T'$$$ 中 $$$a_i$$$ 的最小值,$$$C$$$ 为 $$$T'$$$ 中 $$$c_i$$$ 的最小值。设 $$$B$$$ 为 $$$T'$$$ 中 $$$b_i$$$ 的总和,$$$D$$$ 为 $$$T'$$$ 中 $$$d_i$$$ 值的总和。令 $$$\min(A, C) \cdot (B + D)$$$ 为 $$$T'$$$ 的成本。您需要找到 $$$T'$$$ 的最大可能成本。
输入
第一行包含一个整数 $$$n$$$ ($$$3\le n \le 2\cdot 10^5$$$) — 树 $$$T$$$ 中的顶点数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 2\cdot 10^5$$$),其中第 $$$i$$$ 个整数表示第 $$$i$$$ 个顶点的 $$$a_i$$$ 值。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i\le 2\cdot 10^5$$$),其中第 $$$i$$$ 个整数表示第 $$$i$$$ 个顶点的 $$$b_i$$$ 值。
接下来是 $$$n-1$$$ 行,其中第 $$$j$$$ 行包含四个整数 $$$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$$$) 表示边缘$$$(x_j,y_j)$$$ 及其值分别为$$$c_j$$$ 和$$$d_j$$$。保证边形成一棵树。
输出
打印一个整数 — $$$T'$$$ 的最大可能成本。
示例
输入 #1
3 1 2 2 1 1 2 1 2 2 1 1 3 1 2
输出 #1
8
输入 #2
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
输出 #2
35
输入 #3
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
输出 #3
216
输入#4
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
输出#4
7000000
注意
语句中显示了第一个示例中的树。
第二个示例的树如下所示:
$$$A = 1,B = 18,C = 1,D = 17$$$,因此成本为 $$$\min(1,1) \cdot (18 + 17) = 35$$$。