#P5951. [Usaco2022 Open]Balancing a Tree G

    ID: 4951 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理二分答案动态规划树形 DP构造与建模不变量分析CF2300

[Usaco2022 Open]Balancing a Tree G

题目描述

Farmer John 用一棵有根树描述牛品种的演化。树的 NN 个节点编号为 11 到 NN,节点 11 为根。节点 ii(2≤i≤N2\le i\le N)的父节点为 pip_i。节点 ii 的祖先包括它的父节点及其父节点的所有祖先。

第 ii 个品种身上有整数个斑点 sis_i,并且 sis_i 必须在给定区间 [li,ri][l_i,r_i] 内。树的不平衡度是所有「节点与其祖先」点对的 ∣si−sj∣\lvert s_i-s_j\rvert 的最大值。

给每个节点选定斑点数,使不平衡度最小。按输入中的 BB 决定是否同时输出一组达到最小值的方案。

输入格式

第一行两个整数 T,BT,B,满足 1≤T≤101\le T\le10、B∈{0,1}B\in\{0,1\}。

每组数据第一行一个整数 NN(2≤N≤1052\le N\le10^5),第二行 N−1N-1 个整数 p2,…,pNp_2,\ldots,p_N(1≤pi<i1\le p_i<i)。

接下来 NN 行,第 ii 行两个整数 li,ril_i,r_i(0≤li≤ri≤1090\le l_i\le r_i\le10^9)。所有数据组的 NN 之和不超过 10510^5。

输出格式

每组数据先输出一行,表示最小不平衡度。若 B=1B=1,再输出一行 NN 个用空格分隔的整数 s1,…,sNs_1,\ldots,s_N,给出任意一组达到该不平衡度的合法方案。

样例 #1

样例输入 #1

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

样例输出 #1

3
1
4

样例解释 #1

第一组数据的最小不平衡度是 33,可以取 [s1,s2,s3]=[4,1,7][s_1,s_2,s_3]=[4,1,7]。

样例 #2

样例输入 #2

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

样例输出 #2

3
3 1 6
1
6 5 5 5 5
4
5 1 9

样例解释 #2

与第一份样例相比,只改变了 BB。对于第一组数据,样例给出了另一个达到不平衡度 33 的方案 [3,1,6][3,1,6]。

测试点性质

  • 测试点 3–4 中,每个 ii 都满足 li=ril_i=r_i。
  • 测试点 5–6 中,每个 i≥2i\ge2 都满足 pi=i−1p_i=i-1。
  • 测试点 7–16 无额外限制。
  • 每个子任务中,前一半测试点满足 B=0B=0,后一半满足 B=1B=1。