题目描述

译自 ROI 2022 Day1 T2. Оптимизация закупок

滑雪装备租赁网是一个由 $n$ 个节点组成的有根树，节点从 $1$ 到 $n$ 编号，根节点为 $1$ 号节点。每个节点都有一个租赁点。位于 $i$ 号节点的租赁点以 $c_i$ 卢布的价格购买一套装备。

设 $a_i$ 是所有位于 $i$ 号节点子树中的租赁点购买的滑雪装备套数的总和。根据市场调查，对于每个 $i$，$a_i$ 应该满足 $l_i \le a_i \le r_i$。

需要确定每个租赁点在季节开始时需要购买多少套装备，使得对于网络中任意节点的子树，总套数都在市场人员指定的范围内，而且所有购买的装备的总价格尽可能低。或者确定无法满足市场人员的所有条件。

输入格式

输入包含多组数据。第一行包含一个整数 $t\ (1 \leq t \leq 5\cdot 10^4)$，表示测试数据的组数。

每组输入数据的第一行包含一个整数 $n\ (1 \le n \le 10^5)$，表示树中节点的数量。

在第二行中给出 $n - 1$ 个整数 $p_2, p_3, \ldots, p_n\ (1 \le p_i < i)$，表示节点 $i$ 的父节点是节点 $p_i$。

在下一行中给出 $n$ 个整数 $c_1, \ldots, c_n$ ($1 \le c_i \le 10^9$)，其中 $c_i$ 是节点 $i$ 的租赁点购买一套装备的价格。

在接下来的 $n$ 行中，每行给出两个整数 $l_i, r_i\ (0 \le l_i \le r_i \le 10^9)$，表示在节点 $i$ 的子树中的租赁点购买的滑雪装备套数的总和的限制。

保证所有输入数据组中的 $n$ 之和不超过 $10^5$。

输出格式

对于每组输入数据，按照以下格式输出答案。

如果无法满足市场人员的所有条件，输出 $-1$。

否则，在第一行中输出所有租赁点网络购买滑雪装备的最小总价格。在第二行中输出 $n$ 个整数 $b_i$，其中 $b_i$ 等于节点 $i$ 的租赁点需要购买的套数。如果有多种方式满足市场人员的所有条件，同时使总价格最低，您可以输出其中任意一种。

2
3
1 1
3 1 2
5 7
1 2
2 4
2
1
5 5
0 1
2 2

8
0 2 3
-1

下图是示例中第一个输入数据集合的示意图：

总花费的卢布数为 $c_1 \cdot b_1 + c_2 \cdot b_2 + c_3 \cdot b_3 = 0 + 2 + 6 = 8$。

数据范围与提示

设所有输入数据集合中节点的总数为 $\sum n$。设节点 $i$ 的子树中节点的数量为 $s_i$。