#P5951. [Usaco2022 Open]Balancing a Tree G
[Usaco2022 Open]Balancing a Tree G
题目描述
Farmer John 用一棵有根树描述牛品种的演化。树的 个节点编号为 到 ,节点 为根。节点 ()的父节点为 。节点 的祖先包括它的父节点及其父节点的所有祖先。
第 个品种身上有整数个斑点 ,并且 必须在给定区间 内。树的不平衡度是所有「节点与其祖先」点对的 的最大值。
给每个节点选定斑点数,使不平衡度最小。按输入中的 决定是否同时输出一组达到最小值的方案。
输入格式
第一行两个整数 ,满足 、。
每组数据第一行一个整数 (),第二行 个整数 ()。
接下来 行,第 行两个整数 ()。所有数据组的 之和不超过 。
输出格式
每组数据先输出一行,表示最小不平衡度。若 ,再输出一行 个用空格分隔的整数 ,给出任意一组达到该不平衡度的合法方案。
样例 #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
第一组数据的最小不平衡度是 ,可以取 。
样例 #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
与第一份样例相比,只改变了 。对于第一组数据,样例给出了另一个达到不平衡度 的方案 。
测试点性质
- 测试点 3–4 中,每个 都满足 。
- 测试点 5–6 中,每个 都满足 。
- 测试点 7–16 无额外限制。
- 每个子任务中,前一半测试点满足 ,后一半满足 。