题面下载

样例下载

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

为了在“曙梦星海”的各大拓荒据点之间建立稳定的通信，“曙梦号”总工程师小梦正在设计一套呈现树形拓扑的量子通信网络。由于星际空间存在宇宙射线干扰，通信链路的稳定性存在波动，小梦必须合理规划中继基站的位置，以最小化总建设与传输成本。

题目描述

星海的通信网络呈现为一个以据点 $1$ 为根、$n$ 个据点组成的有根树。树上的边代表节点间的数据传输链。

对于所有据点 $u$，小梦需要分别计算出从据点 $1$ 向 $u$ 输送数据的最少成本。

每条数据链可以用一个四元组 $(u,v,r,p)$ 表示，意味着在节点 $u$ 和 $v$ 之间有一条数据链。在有根树中 $u$ 总是 $v$ 的父节点，且满足 $u<v$。由于宇宙射线的干扰，这条数据链的传输长度有 $p$ 的概率为 $r$（无噪声状态），有 $1-p$ 的概率为 $2r$（有噪声状态）。

为了增强信号，每个节点都可以建立一个量子中继基站，在节点 $i$ 建立中继站的建设代价是 $c_i$。

对于相邻的两个中继站（即这两个节点的路径上不存在其他中继站），它们之间传输数据的“直连成本”定义为路径上链路长度之和的平方的期望：

$$E\left[(\sum_{e\in \text{path}(u,v)}X_e)^2 \right] $$

其中 $X_e$ 表示以边 $e$ 的实际数据链长度为变量。

从节点 $1$ 到节点 $u$ 传输数据的总成本定义为：路径上（包含端点）建立的所有中继站的建设代价之和 加上 所有相邻两个中继站之间的数据直连传输成本之和。

特别规定：在向 $u$ 传输数据时，起点 $1$ 和终点 $u$ 必须建立为中继站。

输入格式

从标准输入读入数据。

第一行一个整数 $n$。

第二行 $n$ 个浮点数 $c_1,\cdots,c_n$。

接下来 $n-1$ 行，每行四个数值 $u,v,r,p$，代表每一条数据链。

所有的浮点数（$c_i,r,p$）保证小数点后恰好是两位。

输出格式

输出到标准输出。

输出 $n$ 行，第 $i$ 行一个浮点数，表示从节点 $1$ 到节点 $i$ 的数据传输最小成本。

每个点你的输出答案与标准答案的绝对或相对误差在 $10^{-6}$ 以内即为正确。

4
1.00 3.00 2.00 4.00
1 2 1.00 0.50
2 3 1.00 0.50
1 4 2.00 0.50

1.00
6.50
11.00
15.00

样例 1 解释

样例当中的量子通信网络如下：

• 从 $1$ 到 $1$：只需付出建立 $1$ 为中继站的费用 $c_1=1.00$。
• 从 $1$ 到 $2$：起点 $1$ 和终点 $2$ 必须建站。总成本 = $c_1 + c_2 + E[X_{12}^2] = 1.00 + 3.00 + 2.50 = 6.50$。
• 从 $1$ 到 $3$：
  • 方案 A（不在 $2$ 建站）：直接从 $1$ 连到 $3$。直连成本 $E[(X_{12}+X_{23})^2]$ 可拆解为 $Var(X_{12}) + Var(X_{23}) + (E[X_{12}]+E[X_{23}])^2 = 0.25 + 0.25 + (1.5+1.5)^2 = 9.50$。总成本 = $c_1 + c_3 + 9.50 = 1.00 + 2.00 + 9.50 = 12.50$。
  • 方案 B（在 $2$ 建站）：作为两个独立直连段。总成本 = $c_1 + c_2 + c_3 + E[X_{12}^2] + E[X_{23}^2] = 1.00 + 3.00 + 2.00 + 2.50 + 2.50 = 11.00$。
  • 综上，最小成本为 $11.00$。
• 从 $1$ 到 $4$：必须在 $1$ 和 $4$ 建站。总成本 = $c_1 + c_4 + E[X_{14}^2] = 1.00 + 4.00 + 10.00 = 15.00$。

子任务

对于所有数据：

• $1\le n\le 10^5$；
• $p\in [0,1]$；
• $c_i\le 10^6$；
• $r\le 100$；
• $1\le u<v\le n$；
• 输入的浮点数均为 2 位小数

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n\le$	特殊性质
1	20	$20$	无
2	10	$5000$	从 $1$ 到任何节点都最多只有两条数据链
3	20		无
4		$10^5$	保证所有点构成一条链
5	30		无