P6966: 平衡树
传统题
1.000s
时间限制
256MB
内存限制
3 提交
0 解决
【题目描述】
【题目描述】
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
。