{"problem":{"name":"[_-0 B] 地铁","description":{"content":"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 市政府决定开通一条地铁线路。地铁线路是树上的一","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9476"},"statements":[{"statement_type":"Markdown","content":"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)$ 的时间。\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## Input\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## Output\n\n一行，一个整数，表示所求的最小值。\n\n答案可能超过 $64$ 位整形表示范围，您可以使用 `__int128` 类型，其表示范围为 $[-2^{127},2^{127}-1]$。\n\n以下为 `__int128` 类型的输出模板：\n\n```cpp\n#include <bits/stdc++.h>\nusing namespace std;\n__int128 ans;\nint main() {\n    /* Your code here */\n    string str;\n    if (!ans) {\n        str = \"0\";\n    } else {\n        str = \"\";\n        while (ans) {\n            str = ((char)(48 + ans % 10)) + str;\n            ans /= 10;\n        }\n    }\n    cout << str << endl;\n    return 0;\n}\n```\n\n[samples]\n\n## Background\n\n小 $\\mathfrak{f}$ 的家乡 A 市最近开通了地铁。\n\n## Note\n\n**样例 $1$ 解释：**\n\n修建地铁前如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/3oh0y5mn.png)\n\n一种最优的修建地铁的方案为从 $2$ 到 $3$ 修建地铁。如下图所示（实线表示修建了地铁）：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ian9c6po.png)\n\n从 $1$ 到 $2$ 经过地铁，所需时间为：$6+0=6$，对答案的贡献为：$9\\times9\\times6=486$。\n\n从 $1$ 到 $3$ 经过地铁，所需时间为：$5+0=5$，对答案的贡献为：$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$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9476","tags":["动态规划 DP","O2优化","动态规划优化","斜率优化","树形 DP"],"sample_group":[["0 5 0\n9\n9\n3\n2\n3\n1 2 7 6\n1 3 8 5\n1 4 6 5\n2 5 9 9","2262"],["0 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","33600416"]],"created_at":"2026-03-03 11:09:25"}}