地铁 - 最优地铁线路规划 - 算法题解

{/'title/':/'# [-0 B] 地铁//n//n## 题目背景//n//n小 //u2044//u2113 的家乡 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现在，小 //u2044//u2113 想知道在所有 $//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$//n//n用C++解内容：cpp//n#include <iostream>//n#include <vector>//n#include <cstdint>//n#include <algorithm>//nusing namespace std;//n//n#define type long long//n//nstruct Edge {//n//tint u, v;//n//ntype w, w_prime;//n};//n//ntype ans = 0;//nvector<int> size, pop;//nvector<Edge> edges;//nvector<vector<int>> adj;//n//nvoid dfs(int u, int p) {//n//tsize[u] = pop[u];//n//tfor (int v : adj[u]) {//n//t//tif (v == p) continue;//n//t//tdfs(v, u);//n//t//tans += 2 * size[u] * size[v] * edges[u].w;//n//t//tsize[u] += size[v];//n//t}//n}//n//nvoid solve(int n, int t) {//n//tsize.resize(n+1);//n//tpop.resize(n+1);//n//tadj.resize(n+1);//n//tfor (int i = 1; i <= n; ++i) {//n//t//tcin >> pop[i];//n//t}//n//tfor (int i = 1; i < n; ++i) {//n//t//tint u, v, w, w_prime;//n//t//tcin >> u >> v >> w >> w_prime;//n//t//tedges.push_back({u, v, w, w_prime});//n//t//tadj[u].push_back(v);//n//t//tadj[v].push_back(u);//n//t}//n//tdfs(1, 0);//n//tfor (int i = 0; i < edges.size(); ++i) {//n//t//tint u = edges[i].u, v = edges[i].v;//n//t//tif (u > v) swap(u, v);//n//t//ntype delta = edges[i].w - edges[i].w_prime;//n//t//tans -= 2 * size[u] * size[v] * delta;//n//t}//n//tcout << ans + t * (type(n-1) * (n-2) / 2) << endl;//n}//n//nint main() {//n//tint id, n, t;//n//tcin >> id >> n >> t;//n//tsolve(n, t);//n//treturn 0;//n}//n