| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 131 | 53 | 46 | 48.421% |
Farmer John has conducted an extensive study of the evolution of different cow breeds. The result is a rooted tree with $N$ (2ドル\le N\le 10^5$) nodes labeled 1ドル\ldots N,ドル each node corresponding 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$. A node $j$ is called an ancestor of node $i$ if $j=p_i$ or $j$ is an ancestor of $p_i$.
Every node $i$ in the tree is associated with a breed having an integer number of spots $s_i$. The "imbalance" of the tree is defined to be the maximum of $|s_i-s_j|$ over all pairs of nodes $(i,j)$ such that $j$ is an ancestor of $i$.
Farmer John doesn't know the exact value of $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]$ (0ドル\le l_i\le r_i\le 10^9$) to each node such that the imbalance of the tree is minimized.
The first line contains $T$ (1ドル\le T\le 10$), the number of independent test cases to be solved, and an integer $B\in \{0,1\}$.
Each test case starts with a line containing $N,ドル followed by $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 test cases does not exceed 10ドル^5$.
For each test case, output one or two lines, depending on the value of $B$.
The first line for each test case should contain the minimum imbalance.
If $B=1,$ then print an additional line with $N$ space-separated integers $s_1,s_2,\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
For the first test case, the minimum imbalance is 3ドル$. One way to achieve imbalance 3ドル$ is to set $[s_1,s_2,s_3]=[4,1,7]$.
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
This input is the same as the first one aside from the value of $B$. Another way to achieve imbalance 3ドル$ is to set $[s_1,s_2,s_3]=[3,1,6]$.