← 返回题目列表

Codeforces · 1824/E

E. 洛天依与墨盒

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

洛天依正在看动漫《深渊制造》。她发现制作墨盒很有趣。为了更清楚地描述制作墨盒的过程,她抽象了原始问题并给出了以下问题。

给你一棵树 $$$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$$$。