CF566C Logistical Questions

某国由 $n$ 个城市组成，这些城市通过铁路网络连接。该国的交通网络极为发达，铁路网只包含所需的最少数量——$n-1$ 条双向道路（换句话说，道路构成的图是一棵树）。第 $i$ 条直接连接城市 $a_i$ 与 $b_i$ 的道路，其长度为 $l_i$ 公里。 该交通网络由国有运输公司 FRR（Fabulous Rail Roads）运营。为简化票价政策，公司提供单次乘车票价。要乘坐长度为 $t$ 公里的路线，需要支付  布尔币。注意，不允许将一段长路线拆分为多段短路程分别购票（铁路警察 RRP 会监督以防这一违规行为发生）。 一家大型软件公司决定举办一次编程大赛。经过几轮线上赛，公司已确定了最终入围者名单，并将名单交给后勤部门以选定决赛举办城市。由于公司可以轻松地在国内任一城市举办决赛，选址的主要因素就是为所有决赛入围者购票所需的总费用。已知第 $i$ 个城市有 $w_i$ 名入围者居住。 请帮助公司职员找到一个城市，使得所有决赛入围者前往该城市的总交通费用最小。

输入的第一行为一个整数 $n$（$1\leq n\leq 200\,000$），表示该国的城市数量。 第二行为 $n$ 个整数 $w_1, w_2, ..., w_n$（$0\leq w_i\leq 10^8$），表示每个城市居住的决赛入围者人数。 接下来的 $n-1$ 行，每行包含三个整数，$a_i, b_i, l_i$（$1\leq a_i, b_i\leq n$，$a_i\neq b_i$，$1\leq l_i\leq 1000$），表示第 $i$ 条铁路直接连接城市 $a_i$ 和 $b_i$，长度为 $l_i$ 公里。

输出两个数——一个整数 $f$，表示举办比赛的最优城市编号，以及一个实数 $c$，表示将所有决赛选手运送到该城市的最小总费用。当且仅当同时满足下列两项，答案才被认为是正确的： 1. 输出的 $c$ 与将决赛安排在城市 $f$ 时的费用比较，绝对误差或相对误差不超过 $10^{-6}$； 2. 输出的 $c$ 与标准答案相比，绝对误差或相对误差不超过 $10^{-6}$。 如果有多个答案，可以任选一个输出。

在样例测试中，将决赛举办城市选为 $3$ 是最优选择，在这种情况下的费用是  布尔币。 在第二个样例测试中，无论选择哪个城市，均需为五位选手支付交通费用，对每个人的费用都是  布尔币。 由 ChatGPT 5 翻译