P11097 [ROI 2022] 采购优化 (Day 1)

翻译自 [ROI 2022 D1T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-roi-2022-day1.pdf)。

租赁滑雪设备的网点网络是一棵根节点为 $1$ 的树，由 $n$ 个节点组成，编号从 $1$ 到 $n$。每个节点上都有一个租赁点。位于第 $i$ 个节点的租赁点需要以 $c_i$ 卢布的价格购买设备套件。 设 $a_i$ 表示在位于节点 $i$ **子树的所有租赁点中**将要购买的滑雪设备套件的总数。根据市场调研，这个值必须要满足 $l_i\le a_i\le r_i$。 需要确定在赛季开始时每个租赁点需要购买多少套设备，以便对于网络中任何一个子树，设备套件的总数量都在市场营销人员指定的范围内，并且购买的所有设备套件的总成本最小，或是否不可能满足所有市场营销条件。

每个测试点包含多个测试数据。第一行给出一个整数 $t$，表示测试数据的数量。接下来是 $t$ 个测试数据。 每个测试数据的第一行给出一个整数 $n$（$1\le n\le10^5$），表示树中的节点数量。 接下来一行给出 $n-1$ 个整数 $p_2,p_3,\dots,p_n$（$1\le p_i

对于每个测试数据，以下面的格式输出答案。 如果无法满足所有市场营销条件，请输出 `-1`。 否则，在第一行中输出购买整个网络的滑雪设备需要花费的最小卢布数。在第二行中，输出 $n$ 个整数 $b_i$，其中 $b_i$ 表示编号为 $i$ 的租赁点需要购买的设备套件的数量。如果有多种方式以最小的成本满足所有市场营销条件，可以输出其中一种。

样例输入的第一组数据说明：  $c_1 b_1 + c_2 b_2 + c_3 b_3 = 0 + 2 + 6 = 8$。 数据范围： 设节点 $i$ 的子树中的节点数量为 $s_i$。 | Subtask | 分值 | $\sum n\le$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $24$ | $500$ | $r_i\le1000$ | | $2$ | $22$ | $5000$ | $r_i\le s_i$ | | $3$ | $18$ | $10^5$ | $l_i\le100\times s_i$，$r_i=10^9$ | | $4$ | $21$ | $5000$ | | | $5$ | $15$ | $10^5$ | | 全部数据范围见输入格式。