P13900 [CSPro 28] 聚集方差

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。 通常而言，对一组数据 $A = \{a_1, ..., a_n\}$，可以使用方差 $\sigma^2(A) = \frac{1}{n} \sum_{i=1}^{n} (a_i - \mu(A))^2$ 来衡量其离散程度（其中 $\mu(A) = \frac{1}{n} \sum_{i=1}^{n} a_i$ 为平均值），或者说“整体聚集”的程度。然而，现实生活中的数据有时是“分组聚集”的——它们可以被分为若干组，每一组都是相对“聚集”的，但不同组间差距较大，因此整体相对离散。此时，方差无法反映这种分组聚集的性质，而人为指定分组的情况则使计算复杂。为此，可以提出一种简单的衡量方式：称一组数据 $A = \{a_1, a_2, ..., a_n\}$ 的“聚集方差”为： $$\mathcal{G}(A) = \frac{1}{n} \sum_{i=1}^{n} \min_{j=1, j \neq i}^{n} (a_i - a_j)^2$$ 特别的，当 $n = |A| = 1$ 时，规定 $\mathcal{G}(A) = 0$。 例如，对 $A = \{0, 0, 0, 4, 4, 4, 7, 8, 9\}$，则方差 $\sigma^2(A) = \frac{98}{9} \simeq 10.89$，但 $\mathcal{G}(A) = \frac{1}{3} \simeq 0.33$，说明若 $A$ 按 $\{0, 0, 0\}, \{4, 4, 4\}, \{7, 8, 9\}$ 的方式分组，则相对与整体而言，每一组内都相对聚集。

考虑这样一个模型：现实中一个公司的结构可以用一棵有根树来描述，其中每个点对应一位员工，其父节点（如果有的话）代表了他的直属上司，而其自子树中的点（包括这个点本身）则代表所有可被他支配的员工（广义的讲，人可以支配自己，因此人可以视为自己的员工，因此此处“员工”的概念包括他自己本人）。 一般地，假定该公司内有 $n$ 位员工，编号从 1 到 $n$；对编号为 $x$ 的员工，记 $T(x)$ 为其子树内所有点的编号的集合（包括 $x$ 本身）。 对 $x > 1$，记 $p_x$ 为其父节点的编号，并假定总有 $1 \leq p_x < x$（从而编号为 1 的员工是该公司唯一的老板）。 我们说明“聚集方差”可以作为一种统计方式帮助该公司的老板了解他的公司，例如，假定每个员工每年都有一小时的可以自主选择时间的带薪年假，那么可以根据历史数据，统计出每位员工偏好的时间；对第 $x$（$1 \leq x \leq n$）位员工，可以用一个非负整数 $a_x$ 表示其偏好的时间。 记 $A(x) = \{a_y : y \in T(x)\}$ 为编号为 $x$ 的点的子树内所有点（包括 $x$）对应员工的偏好时间的可重集合（从而 $|A(x)| = |T(x)|$）。那么，对于一位编号为 $x$ 的员工，若其可支配的员工偏好的时间的聚集方差 $\mathcal{G}(A(x)) = \frac{1}{|T(x)|} \sum_{y \in T(x)} \min_{z \in T(x), z \neq y} (a_z - a_y)^2$ 较小，那么说明他可能需要担心会因在某个时间有较多的员工请假而导致工作任务受到影响，从而应该调整工作日程以避免这一问题；反之则说明他不太需要过多关注这一点。 因此该公司的老板想了解，对每个 $x \in [1, n]$，$\mathcal{G}(A(x))$ 是多少？当然，为了避免精度误差，你只需要输出 $V_x = |T(x)| \mathcal{G}(A(x))$。容易验证 $V_x$ 总是整数。

从标准输入读入数据。 第一行输入一个正整数 $n$ 表示树的大小； 接下来一行输入 $n - 1$ 个正数依次表示 $p_2, \ldots, p_n$； 接下来一行输入 $n$ 个非负整数依次表示 $a_1, \ldots, a_n$。

输出到标准输出。 输出 $n$ 行，其中第 $i$ 行包含一个非负整数表示 $V_i$。

### 子任务 ::cute-table{tuack} | 子任务编号 | $n \leq$ | 特殊性质 | 子任务分值 | | :-: | :-: | :-: | :-: | | 1 | $300$ | / | 15 | | 2 | $3\,000$ | ^ | 25 | | 3 | $3 \times 10^{5}$ | A | 15 | | 4 | ^ | B | ^ | | 5 | ^ | C | 10 | | 6 | ^ | / | 20 | 特殊性质 A: $\forall i \in (1, n], p_i = i - 1$。 特殊性质 B: $\forall i \in (1, n], p_i = \lfloor \frac{i}{2} \rfloor$。 特殊性质 C: $\forall i, j \in [1, n], i \neq j \Rightarrow a_i \neq a_j$。 对于所有的数据保证：$2 \leq n \leq 3 \times 10^{5}$, $\forall i \in (1, n], p_i \in [1, i)$; $\forall i \in [1, n], a_i \in [0, 10^{9}]$。