题目描述
【题目描述】
Farmer John 对不同奶牛品种的进化进行了广泛的研究。所得到的结果形成一棵 N（2≤N≤10^5）个结点的有根树，编号为 1…N，每个结点对应一个奶牛品种。对于每一个i∈[2,N]，结点 i 的父结点是结点 pi（1≤pi<i），意味着品种 i 是由品种 pi 进化而来的。称结点 j 为结点 i 的祖先，如果 j=pi 或者 j 是 pi 的祖先。
树中的结点 i 所关联的品种具有整数 si 数量的斑点。定义树的「不平衡度」为所有结点对 (i,j) 中 |si−sj| 的最大值，其中 j 是 i 的祖先。
Farmer John 不知道每个品种的 si 的确切数值，但他知道这些值的下界和上界。你的任务是为每个结点分配一个整数值 si∈[li,ri]（0≤li≤ri≤10^9），以最小化树的不平衡度。
【输入格式】（从终端 / 标准输入读入）：
输入的第一行包含 T（1≤T≤101≤T≤10），为需要独立求解的子测试用例的数量，以及一个整数B∈{0,1}。
每个子测试用例的第一行包含 N，第二行包含N−1 个整数p2,p3,…,pN。
以下 N 行每行包含两个整数 li 和 ri。
输入保证所有子测试用例的 N 之和不超过 10^5。
【输出格式】（输出至终端 / 标准输出）：
对每个子测试用例，根据 B 的值输出一行或两行。
每个子测试用例的第一行包含最小不平衡度。
如果 B=1，则再输出一行，包含 N 个空格分隔的整数 s1,s2,…,sN，为达到以上不平衡度的一种斑点数量的分配方式。任何合法的分配方式均正确。
【输入样例】：
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。一种达到不平衡度 3 的方式是令 [s1,s2,s3]=[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
【样例说明】
这个测试用例除了 B 的值之外与第一个测试用例完全相同。另一种达到不平衡度 3 的方式是令 [s1,s2,s3]=[3,1,6]。
【测试点性质】：
测试点 3-4 对于所有的 i 满足 li=ri。
测试点 5-6 对于所有的 i 满足 pi=i−1。
测试点 7-16 没有额外限制。
在每一部分子任务中，前一半的测试点满足 B=0，后一半测试点满足 B=1。