[_-0 B] 地铁

小 $\mathfrak{f}$ 的家乡 A 市最近开通了地铁。

A 市共有 $n (2\le n \le 10^5)$ 个居民点，第 $i$ 个居民点的人口为 $s_i (1 \le s_i \le 10^7)$，同时有 $n-1$ 条双向道路，构成一棵树，第 $i $ 条双向道路连接居民点 $u_i$ 和 $v_i$，人步行走过这条道路需要 $w_i (1 \le w_i\le 10^7)$ 的时间。 现 A 市政府决定开通一条地铁线路。地铁线路是树上的一条简单路径，若路径经过第 $i$ 条道路，那么地铁从这条道路下方经过只需要 $w_i^{\prime} (1 \le w_i^{\prime} \le 10^7)$ 的时间，同时，地铁的进出站**共**需要花费 $t (0 \le t \le 10^7)$ 的时间。 已知，若一个人从一个居民点前往另一个居民点，如果这条路径与地铁经过的路径有至少一条公共**边**，那么就**一定**会选择**尽可能多地**乘坐地铁。如果没有公共边，那么就会选择完全步行。**题目保证对于第 $i$ 条道路有 $w_i^{\prime} \le w_i - t$。** 我们认为，如果两个居民点的人口的乘积越大，那么有人想要在它们之间流动的可能性也越大。 现在，小 $\mathfrak{f}$ 想知道在所有 $\frac{n(n-1)}{2}$ 种建造地铁线路的方案中，$\sum_{a=1}^{n-1}\sum_{b=a+1}^{n}(s_a \cdot s_b \cdot d_{a,b})$ 的最小值，其中 $d_{a,b}$ 表示从居民点 $a$ 前往 $b$（或者从 $b$ 前往 $a$，两者是相等的）所需要的时间。 但是他不会，所以他来求助万能的你。

第一行，三个用空格分隔的整数 $id,n,t$，表示子任务编号，居民点个数和进出站所需要花费的时间。 接下来 $n$ 行，每行一个整数 $s_i$，表示每个居民点的人口。 接下来 $n - 1$ 行，每行四个用空格分隔的整数 $u_i,v_i,w_i,w_i^{\prime}$，表示每条道路的两个端点，步行所需时间和地铁所需时间。

一行，一个整数，表示所求的最小值。 答案可能超过 $64$ 位整形表示范围，您可以使用 `__int128` 类型，其表示范围为 $[-2^{127},2^{127}-1]$。 以下为 `__int128` 类型的输出模板： ```cpp #include <bits/stdc++.h> using namespace std; __int128 ans; int main() { /* Your code here */ string str; if (!ans) { str = "0"; } else { str = ""; while (ans) { str = ((char)(48 + ans % 10)) + str; ans /= 10; } } cout << str << endl; return 0; } ```

0 5 0
9
9
3
2
3
1 2 7 6
1 3 8 5
1 4 6 5
2 5 9 9

2262

0 10 86
50
6
84
50
83
67
93
55
93
70
1 2 94 7
1 3 97 4
1 10 98 12
2 4 89 1
2 7 98 1
4 5 99 13
4 6 96 5
5 8 95 5
5 9 97 7

33600416

**样例 $1$ 解释：** 修建地铁前如下图所示：  一种最优的修建地铁的方案为从 $2$ 到 $3$ 修建地铁。如下图所示（实线表示修建了地铁）：  从 $1$ 到 $2$ 经过地铁，所需时间为：$6+0=6$，对答案的贡献为：$9\times9\times6=486$。 从 $1$ 到 $3$ 经过地铁，所需时间为：$5+0=5$，对答案的贡献为：$9\times3\times5=135$。 从 $1$ 到 $4$ 不经过地铁，所需时间为：$6$，对答案的贡献为：$9\times2\times6=108$。 从 $1$ 到 $5$ 经过地铁，所需时间为：$6+9+0=15$，对答案的贡献为：$9\times3\times15=405$。 从 $2$ 到 $3$ 经过地铁，所需时间为：$6+5+0=11$，对答案的贡献为：$9\times3\times11=297$。 从 $2$ 到 $4$ 经过地铁，所需时间为：$6+6+0=12$，对答案的贡献为：$9\times2\times12=216$。 从 $2$ 到 $5$ 不经过地铁，所需时间为：$9$，对答案的贡献为：$9\times3\times9=243$。 从 $3$ 到 $4$ 经过地铁，所需时间为：$5+6+0=11$，对答案的贡献为：$3\times2\times11=66$。 从 $3$ 到 $5$ 经过地铁，所需时间为：$5+6+9+0=20$，对答案的贡献为：$3\times3\times20=180$。 从 $4$ 到 $5$ 经过地铁，所需时间为：$6+6+9+0=21$，对答案的贡献为：$2\times3\times21=126$。 综上，答案为：$486+135+108+405+297+216+243+66+180+126=2262$。 可以证明不存在更优的修建地铁的方案。 **本题采用捆绑测试且使用子任务依赖。** | 编号 | 分值 | $n \le$ | 性质 | 依赖 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $0$ | $0$ | N/A | 样例 | 无 | | $1$ | $5$ | $10$ | 无 | 无 | | $2$ | $5$ | $500$ | 无 | $1$ | | $3$ | $10$ | $5000$ | 无 | $1,2$ | | $4$ | $30$ | $10^5$ | A | 无 | | $5$ | $5$ | $10^5$ | B | 无 | | $6$ | $20$ | $10^5$ | C | 无 | | $7$ | $15$ | $10^5$ | D | 无 | | $8$ | $10$ | $10^5$ | 无 | $0,1,2,3,4,5,6,7$ | 特殊性质 A：$t=0$ 特殊性质 B：$u_i=i,v_i=i+1$ 特殊性质 C：每一个点的度数都不超过 $100$ 特殊性质 D：$u_i=1,v_i=i+1$