7475: USACO 2022 US Open Contest, Gold —— T3 Balancing a Tree
[Creator : ]
Description
Farmer John 对不同奶牛品种的进化进行了广泛的研究。所得到的结果形成一棵 $N\ (2≤N≤10^5)$ 个结点的有根树，编号为 $1…N$，每个结点对应一个奶牛品种。对于每一个 $i \in [2,N]$，结点 $i$ 的父结点是结点 $p_i\ (1≤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≤l_i≤r_i≤10^9)$，以最小化树的不平衡度。
Farmer John 不知道每个品种的 $s_i$ 的确切数值，但他知道这些值的下界和上界。你的任务是为每个结点分配一个整数值 $s_i \in [l_i,r_i]\ (0≤l_i≤r_i≤10^9)$，以最小化树的不平衡度。
Input
输入的第一行包含 $T\ (1≤T≤10)$，为需要独立求解的子测试用例的数量，以及一个整数 $B \in \{0,1\}$。
每个子测试用例的第一行包含 $N$，
第二行包含 $N−1$ 个整数 $p_2,p_3,…,p_N$。
以下 $N$ 行每行包含两个整数 $l_i,r_i$。
输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。
每个子测试用例的第一行包含 $N$，
第二行包含 $N−1$ 个整数 $p_2,p_3,…,p_N$。
以下 $N$ 行每行包含两个整数 $l_i,r_i$。
输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。
Output
对每个子测试用例，根据 $B$ 的值输出一行或两行。 每个子测试用例的第一行包含最小不平衡度。
如果 $B=1$，则再输出一行，包含 $N$ 个空格分隔的整数 $s_1,s_2,…,s_N$，为达到以上不平衡度的一种斑点数量的分配方式。
任何合法的分配方式均正确。
如果 $B=1$，则再输出一行，包含 $N$ 个空格分隔的整数 $s_1,s_2,…,s_N$，为达到以上不平衡度的一种斑点数量的分配方式。
任何合法的分配方式均正确。
Constraints
测试点 3-4 对于所有的 $i$ 满足 $l_i=r_i$。
测试点 5-6 对于所有的 $i$ 满足 $p_i=i−1$。
测试点 7-16 没有额外限制。
在每一部分子任务中，前一半的测试点满足 $B=0$，后一半测试点满足 $B=1$。
测试点 5-6 对于所有的 $i$ 满足 $p_i=i−1$。
测试点 7-16 没有额外限制。
在每一部分子任务中，前一半的测试点满足 $B=0$，后一半测试点满足 $B=1$。
Sample 1 Input
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
Sample 1 Output
3
1
4
对于第一个子测试用例，最小不平衡度为 $3$。一种达到不平衡度 $3$ 的方式是令 $[s_1,s_2,s_3]=[4,1,7]$。
Sample 2 Input
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
Sample 2 Output
3
3 1 6
1
6 5 5 5 5
4
5 1 9
这个测试用例除了 $B$ 的值之外与第一个测试用例完全相同。另一种达到不平衡度 $3$ 的方式是令 $[s_1,s_2,s_3]=[3,1,6]$。