本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

Farmer John 对不同奶牛品种的进化进行了大量研究。结果得到一棵以根为起点的树，包含 $N$（$2\le N\le 10^5$）个节点，编号为 $1\ldots N$，每个节点对应一种奶牛品种。对于每个 $i\in [2,N]$，节点 $i$ 的父节点为 $p_i$（$1\le p_i<i$），表示品种 $i$ 由品种 $p_i$ 进化而来。若 $j=p_i$ 或 $j$ 是 $p_i$ 的祖先，则称节点 $j$ 是节点 $i$ 的祖先。 树中每个节点 $i$ 关联一个品种，其身上的斑点数为整数 $s_i$。树的“失衡度（imbalance）”定义为：在所有满足 $j$ 是 $i$ 的祖先的节点对 $(i,j)$ 中，$|s_i-s_j|$ 的最大值。 Farmer John 并不知道每个品种的 $s_i$ 的确切值，但知道其上下界。你的任务是为每个节点选择一个整数 $s_i \in [l_i,r_i]$（$0\le l_i\le r_i\le 10^9$），使得整棵树的失衡度最小。

输入格式

第一行包含 $T$（$1\le T\le 10$），表示独立测试用例的数量，以及一个整数 $B\in \{0,1\}$。 每个测试用例先给出一行 $N$，随后给出 $N-1$ 个整数 $p_2,p_3,\ldots,p_N$。 接下来 $N$ 行每行包含两个整数 $l_i$ 和 $r_i$。 保证所有测试用例的 $N$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，根据 $B$ 的取值输出一行或两行。 每个测试用例的第一行输出最小失衡度。 如果 $B=1$，则额外输出一行，包含 $N$ 个用空格分隔的整数 $s_1,s_2,\ldots, s_N$，表示一种达到上述失衡度的斑点数赋值。任意合法赋值都会被接受。

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

提示

对于第一个测试用例，最小失衡度为 $3$。一种达到失衡度 $3$ 的方法是令 $[s_1,s_2,s_3]=[4,1,7]$。 该输入与第一个输入相同，除了 $B$ 的取值不同。另一种达到失衡度 $3$ 的方法是令 $[s_1,s_2,s_3]=[3,1,6]$。 SCORING: 测试用例 3-4 满足对所有 $i$ 都有 $l_i=r_i$。 测试用例 5-6 满足对所有 $i$ 都有 $p_i=i-1$。 测试用例 7-16 没有额外限制。 在每个子任务中，前一半测试用例满足 $B=0$，其余满足 $B=1$。 Problem credits: Andrew Wang

来源

USACO|2022|Gold