Balancing a Tree

문제

Farmer John has conducted an extensive study of the evolution of different cow breeds. The result is a rooted tree with $NN$ ($2\le N\le {10}^{5}2\backslash le\; N\backslash le\; 10^5$) nodes labeled $1\dots N1\backslash ldots\; N$, each node corresponding to a cow breed. For each $i\in [2,N]i\backslash in\; [2,N]$, the parent of node $ii$ is node $p_{i}p\_i$ (), meaning that breed $ii$ evolved from breed $p_{i}p\_i$. A node $jj$ is called an ancestor of node $ii$ if $j=p_{i}j=p\_i$ or $jj$ is an ancestor of $p_{i}p\_i$.

Every node $ii$ in the tree is associated with a breed having an integer number of spots $s_{i}s\_i$. The "imbalance" of the tree is defined to be the maximum of $\mathrm{\mid }{s}_i-s_j\mathrm{\mid }|s\_i-s\_j|$ over all pairs of nodes $(i,j)(i,j)$ such that $jj$ is an ancestor of $ii$.

Farmer John doesn't know the exact value of $s_{i}s\_i$ for each breed, but he knows lower and upper bounds on these values. Your job is to assign an integer value of $s_i\in [l_i,r_i]s\_i\; \backslash in\; [l\_i,r\_i]$ ($0\le l_i\le r_i\le {10}^{9}0\backslash le\; l\_i\backslash le\; r\_i\backslash le\; 10^9$) to each node such that the imbalance of the tree is minimized.

입력

The first line contains $TT$ ($1\le T\le 101\backslash le\; T\backslash le\; 10$), the number of independent test cases to be solved, and an integer $B\in \{0,1\}B\backslash in\; \backslash \{0,1\backslash \}$.

Each test case starts with a line containing $NN$, followed by $N-1N-1$ integers $p_2,p_3,\dots ,p_{N}p\_2,p\_3,\backslash ldots,p\_N$.

The next $NN$ lines each contain two integers $l_{i}l\_i$ and $r_{i}r\_i$.

It is guaranteed that the sum of $NN$ over all test cases does not exceed ${10}^{5}10^5$.

출력

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

The first line for each test case should contain the minimum imbalance.

If $B=1,B=1,$ then print an additional line with $NN$ space-separated integers $s_1,s_2,\dots ,s_{N}s\_1,s\_2,\backslash ldots,\; s\_N$ containing an assignment of spots that achieves the above imbalance. Any valid assignment will be 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