地铁线路规划 - 最小化城市居民点间通行时间

{"title":"# [-0 B] 地铁","description":"给定一个城市的地图，包含居民点和道路，以及地铁线路建设方案，你需要计算出在所有地铁线路方案中，城市居民点间通行时间的最小值。","keywords":"地铁, 城市规划, 最小化, 通行时间, 树, 图论, 动态规划","content":"## 题目背景\n\n小 $\mathfrak{f}$ 的家乡 A 市最近开通了地铁。\n\n## 题目描述\n\nA 市共有 $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)$ 的时间。\n\n现 A 市政府决定开通一条地铁线路。地铁线路是树上的一条简单路径，若路径经过第 $i$ 条道路，那么地铁从这条道路下方经过只需要 $w_i^{\prime} (1 \le w_i^{\prime} \le 10^7)$ 的时间，同时，地铁的进出站共需要花费 $t (0 \le t \le 10^7)$ 的时间。\n\n已知，若一个人从一个居民点前往另一个居民点，如果这条路径与地铁经过的路径有至少一条公共边，那么就一定会选择尽可能多地乘坐地铁。如果没有公共边，那么就会选择完全步行。题目保证对于第 $i$ 条道路有 $w_i^{\prime} \le w_i - t$。 我们认为，如果两个居民点的人口的乘积越大，那么有人想要在它们之间流动的可能性也越大。\n\n现在，小 $\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$，两者是相等的）所需要的时间。\n\n但是他不会，所以他来求助万能的你。\n\n## 输入格式\n\n第一行，三个用空格分隔的整数 $id,n,t$，表示子任务编号，居民点个数和进出站所需要花费的时间。\n\n接下来 $n$ 行，每行一个整数 $s_i$，表示每个居民点的人口。\n\n接下来 $n - 1$ 行，每行四个用空格分隔的整数 $u_i,v_i,w_i,w_i^{\prime}$，表示每条道路的两个端点，步行所需时间和地铁所需时间。\n\n## 输出格式\n\n一行，一个整数，表示所求的最小值。\n\n答案可能超过 $64$ 位整数的表示范围，如果你使用 C++，请使用 __int128 类型，它的表示范围为 $\left[-2^{127},2^{127}-1\right]$。\n\n如果你的计算机中没有 __int128 类型，可以调试的时候 #define type long long，提交的时候改为 #define type __int128。\n\n__int128 类型的运算与 int，long long 类似，但是无法使用 cin/cout/scanf/printf 输入输出。以下提供一种可行的输出方式：\n\ncpp\n__int128 ans;\nstring str;\nwhile (ans) {\n\tstr = (char)((ans % 10) + 48) + str;\n\tans /= 10;\n}\ncout << str << endl;\n\n\n如果你使用 Python，那么恭喜你，Python 的整数自带高精度。\n\n如果你使用其他编程语言，自求多福吧。\n\n## 样例 #1\n\n### 样例输入 #1\n\n\n0 5 0\n9\n9\n3\n2\n3\n1 2 7 6\n1 3 8 5\n1 4 6 5\n2 5 9 9\n\n\n### 样例输出 #1\n\n\n2262\n\n\n## 样例 #2\n\n### 样例输入 #2\n\n\n0 10 86\n50\n6\n84\n50\n83\n67\n93\n55\n93\n70\n1 2 94 7\n1 3 97 4\n1 10 98 12\n2 4 89 1\n2 7 98 1\n4 5 99 13\n4 6 96 5\n5 8 95 5\n5 9 97 7\n\n\n### 样例输出 #2\n\n\n33600416\n\n\n## 提示\n\n样例 $1$ 解释：\n\n修建地铁前如下图所示：\n\n\n\n一种最优的修建地铁的方案为从 $2$ 到 $3$ 修建地铁。如下图所示（实线表示修建了地铁）：\n\n\n\n从 $1$ 到 $2$ 经过地铁，所需时间为：$6+0=6$，对答案的贡献为：$9\times9\times6=486$。\n\n从 $1$ 到 $3$ 经过地铁，所需时间为：$5+0=6$，对答案的贡献为：$9\times3\times5=135$。\n\n从 $1$ 到 $4$ 不经过地铁，所需时间为：$6$，对答案的贡献为：$9\times2\times6=108$。\n\n从 $1$ 到 $5$ 经过地铁，所需时间为：$6+9+0=15$，对答案的贡献为：$9\times3\times15=405$。\n\n从 $2$ 到 $3$ 经过地铁，所需时间为：$6+5+0=11$，对答案的贡献为：$9\times3\times11=297$。\n\n从 $2$ 到 $4$ 经过地铁，所需时间为：$6+6+0=12$，对答案的贡献为：$9\times2\times12=216$。\n\n从 $2$ 到 $5$ 不经过地铁，所需时间为：$9$，对答案的贡献为：$9\times3\times9=243$。\n\n从 $3$ 到 $4$ 经过地铁，所需时间为：$5+6+0=11$，对答案的贡献为：$3\times2\times11=66$。\n\n从 $3$ 到 $5$ 经过地铁，所需时间为：$5+6+9+0=20$，对答案的贡献为：$3\times3\times20=180$。\n\n从 $4$ 到 $5$ 经过地铁，所需时间为：$6+6+9+0=21$，对答案的贡献为：$2\times3\times21=126$。\n\n综上，答案为：$486+135+108+405+297+216+243+66+180+126=2262$。\n\n可以证明不存在更优的修建地铁的方案。\n\n本题采用捆绑测试且使用子任务依赖。\n\n| 编号 | 分值 | $n \le$ | 性质 | 依赖 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $0$ | $0$ | N/A | 样例 | 无 |\n| $1$ | $5$ | $10$ | 无 | 无 |\n| $2$ | $5$ | $500$ | 无 | $1$ |\n| $3$ | $10$ | $5000$ | 无 | $1,2$ |\n| $4$ | $30$ | $10^5$ | A | 无 |\n| $5$ | $5$ | $10^5$ | B | 无 |\n| $6$ | $20$ | $10^5$ | C | 无 |\n| $7$ | $15$ | $10^5$ | D | 无 |\n| $8$ | $10$ | $10^5$ | 无 | $0,1,2,3,4,5,6,7$ |\n\n特殊性质 A：$t=0$\n\n特殊性质 B：$u_i=i,v_i=i+1$\n\n特殊性质 C：每一个点的度数都不超过 $100$\n\n特殊性质 D：$u_i=1,v_i=i+1$