Background

Translated from ROI 2022 D1T2.

Problem Description

The network of ski equipment rental stations is a tree with root node $1$, consisting of $n$ nodes numbered from $1$ to $n$. Each node has a rental station. The station at node $i$ needs to purchase equipment kits at a price of $c_i$ rubles per kit.

Let $a_i$ be the total number of ski equipment kits to be purchased among all rental stations in the subtree of node $i$. According to market research, this value must satisfy $l_i \le a_i \le r_i$.

You need to determine how many kits each rental station should buy before the season starts, so that for any subtree in the network, the total number of kits is within the range specified by the marketing staff, and the total cost of all purchased kits is minimized, or determine that it is impossible to satisfy all marketing requirements.

Input Format

Each test point contains multiple testdata. The first line contains an integer $t$, the number of testdata. Then follow $t$ testdata.

For each testdata, the first line contains an integer $n$ ($1 \le n \le 10^5$), the number of nodes in the tree.

The next line contains $n - 1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$), meaning that the parent of node $i$ is node $p_i$.

The next line contains $n$ integers $c_1, \dots, c_n$ ($1 \le c_i \le 10^9$), where $c_i$ is the price of one equipment kit at station $i$.

The next $n$ lines each contain two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^9$), representing the constraint on the total number of equipment kits within the subtree of node $i$.

It is guaranteed that the sum of $n$ over all testdata does not exceed $10^5$.

Output Format

For each testdata, output the answer in the following format.

If it is impossible to satisfy all marketing requirements, output -1.

Otherwise, on the first line output the minimum number of rubles needed to buy ski equipment for the whole network. On the second line, output $n$ integers $b_i$, where $b_i$ is the number of equipment kits that station $i$ needs to buy. If there are multiple ways to satisfy all marketing requirements with the minimum cost, you may output any one of them.

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

Hint

Explanation of the first test case in the sample input:

$c_1 b_1 + c_2 b_2 + c_3 b_3 = 0 + 2 + 6 = 8$。

Constraints:

Let $s_i$ be the number of nodes in the subtree of node $i$.

The full constraints are given in the Input Format section.

Translated by ChatGPT 5