구매 최적화

스키 장비 대여 네트워크는 루트가 1번 정점인 루트 트리이며, 정점은 $1$부터 $n$까지 번호가 매겨진 $n$개입니다. 각 정점에는 대여소가 하나씩 있고, $i$번 정점의 대여소는 세트당 $c_i$루블에 장비를 구매합니다.

$a_i$를 $i$번 정점의 서브트리에 속한 모든 대여소가 구매하는 장비 세트의 총합이라고 합니다. 마케팅 조사에 따르면 모든 $i$에 대해 $l_i \le a_i \le r_i$여야 합니다.

시즌 시작 전에 각 대여소가 구매할 세트 수를 정하세요. 모든 서브트리의 합이 제한 범위 안에 들어가야 하며, 총 비용은 최소여야 합니다. 마케팅 조건을 모두 만족할 수 없다면 그렇다고 판단하세요.

그래프가 연결되어 있고 사이클이 없으면 트리입니다. 트리의 임의의 두 정점 사이에는 단순 경로가 정확히 하나 있습니다. 루트 트리에는 지정된 루트 정점이 하나 있습니다. 정점 $v$의 서브트리는 루트로 가는 경로에 $v$가 포함되는 모든 정점의 집합이며, $v$ 자신도 포함합니다. 정점 $v$의 부모 $p_v$는 $v$에서 루트로 가는 경로 위에 있으면서 간선으로 $v$와 이어진 정점입니다.

첫 줄에 테스트 케이스 수 $t$가 주어집니다. 각 테스트 케이스의 첫 줄에는 정점 수 $n$ ($1 \le n \le 100000$)이 주어집니다.

둘째 줄에는 $n-1$개의 정수 $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$)이 주어지며, $p_i$는 $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$ 합은 100000을 넘지 않습니다.

각 테스트 케이스에 대해 다음과 같이 답을 출력합니다.

모든 조건을 만족할 수 없다면 한 줄에 $-1$을 출력합니다.

그렇지 않다면 첫 줄에 최소 총 비용(루블)을 출력합니다. 둘째 줄에는 $n$개의 정수 $b_i$를 출력합니다. $b_i$는 $i$번 대여소가 구매할 세트 수입니다. 최소 비용을 달성하는 배치가 여러 개라면 그중 아무것이나 출력해도 됩니다.

아래 그림은 첫 번째 입력 데이터에 대한 것입니다.

총 지출은 $c_1 \cdot b_1 + c_2 \cdot b_2 + c_3 \cdot b_3 = 0 + 2 + 6 = 8$루블입니다.