Background

Thanks to @tiger2005 for providing the SPJ.

Problem Description

Farmer John has done extensive research on the evolution of different cow breeds. The results form a rooted tree with $N$ ($2\le N\le 10^5$) nodes, numbered $1\ldots N$, where each node corresponds to a cow breed. For each $i\in [2,N]$, the parent of node $i$ is node $p_i$ ($1\le p_i< i$), meaning that breed $i$ evolved from breed $p_i$. We call node $j$ an ancestor of node $i$ if $j=p_i$ or $j$ is an ancestor of $p_i$.

The breed associated with node $i$ has an integer number of spots $s_i$. Define the tree's "imbalance" as the maximum value of $|s_i-s_j|$ over all pairs of nodes $(i,j)$ where $j$ is an ancestor of $i$.

Farmer John does not know the exact value of each $s_i$, but he knows a lower bound and an upper bound for each value. Your task is to assign an integer value $s_i \in [l_i,r_i]$ ($0\le l_i\le r_i\le 10^9$) to each node to minimize the imbalance of the tree.

Input Format

The first line of input contains $T$ ($1\le T\le 10$), the number of independent subtest cases to solve, and an integer $B\in \{0,1\}$.

The first line of each subtest case contains $N$. The second line contains $N-1$ integers $p_2,p_3,\ldots,p_N$.

The next $N$ lines each contain two integers $l_i$ and $r_i$.

It is guaranteed that the sum of $N$ over all subtest cases does not exceed $10^5$.

Output Format

For each subtest case, output one or two lines depending on the value of $B$.

The first line of each subtest case contains the minimum imbalance.

If $B=1$, then output an additional line containing $N$ space-separated integers $s_1,s_2,\ldots, s_N$, one assignment of spot counts that achieves the above imbalance. Any valid assignment is accepted.

3 0
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

3
1
4

3 1
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10

3
3 1 6
1
6 5 5 5 5
4
5 1 9

Hint

[Sample Explanation 1]

For the first subtest case, the minimum imbalance is $3$. One way to achieve imbalance $3$ is to set $[s_1,s_2,s_3]=[4,1,7]$.

[Sample Explanation 2]

This subtest case is exactly the same as the first one except for the value of $B$. Another way to achieve imbalance $3$ is to set $[s_1,s_2,s_3]=[3,1,6]$.

[Constraints]

• Test points 3-4: for all $i$, $l_i=r_i$.
• Test points 5-6: for all $i$, $p_i=i-1$.
• Test points 7-16: no additional constraints.

In each subtask, the first half of the test points satisfy $B=0$, and the second half satisfy $B=1$.

Translated by ChatGPT 5