[USACO22OPEN] Balancing a Tree G

感谢 @tiger2005 配置 SPJ。

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$ 为结点 $i$ 的祖先，如果 $j=p_i$ 或者 $j$ 是 $p_i$ 的祖先。 树中的结点 $i$ 所关联的品种具有整数 $s_i$ 数量的斑点。定义树的「不平衡度」为所有结点对 $(i,j)$ 中 $|s_i-s_j|$ 的最大值，其中 $j$ 是 $i$ 的祖先。 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

【样例解释 1】 对于第一个子测试用例，最小不平衡度为 $3$。一种达到不平衡度 $3$ 的方式是令 $[s_1,s_2,s_3]=[4,1,7]$。 【样例解释 2】 这个测试用例除了 $B$ 的值之外与第一个测试用例完全相同。另一种达到不平衡度 $3$ 的方式是令 $[s_1,s_2,s_3]=[3,1,6]$。 【数据范围】 - 测试点 3-4 对于所有的 $i$ 满足 $l_i=r_i$。 - 测试点 5-6 对于所有的 $i$ 满足 $p_i=i-1$。 - 测试点 7-16 没有额外限制。 在每一部分子任务中，前一半的测试点满足 $B=0$，后一半测试点满足 $B=1$。