#PU1235. USACO 2022 US Open Contest, Gold — Problem 3. Balancing a Tree
USACO 2022 US Open Contest, Gold — Problem 3. Balancing a Tree
USACO 2022 US Open Contest, Gold — Problem 3. Balancing a Tree
题目描述
Farmer John has conducted an extensive study of the evolution of different cow breeds. The result is a rooted tree with () nodes labeled , each node corresponding to a cow breed. For each , the parent of node is node (), meaning that breed evolved from breed . A node is called an ancestor of node if or is an ancestor of . Every node in the tree is associated with a breed having an integer number of spots . The "imbalance" of the tree is defined to be the maximum of over all pairs of nodes such that is an ancestor of . Farmer John doesn't know the exact value of for each breed, but he knows lower and upper bounds on these values. Your job is to assign an integer value of () to each node such that the imbalance of the tree is minimized.
输入格式
The first line contains (), the number of independent test cases to be solved, and an integer . Each test case starts with a line containing , followed by integers . The next lines each contain two integers and . It is guaranteed that the sum of over all test cases does not exceed .
输出格式
For each test case, output one or two lines, depending on the value of . The first line for each test case should contain the minimum imbalance. If then print an additional line with space-separated integers containing an assignment of spots that achieves the above imbalance. Any valid assignment will be accepted.
数据范围
Test cases 3-4 satisfy for all . Test cases 5-6 satisfy for all . Test cases 7-16 satisfy no additional constraints. Within each subtask, the first half of the test cases will satisfy , and the rest will satisfy . Problem credits: Andrew Wang
样例
样例 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
3
1
4
For the first test case, the minimum imbalance is $3$. One way to achieve
imbalance $3$ is to set $[s_1,s_2,s_3]=[4,1,7]$.
样例 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
3
3 1 6
1
6 5 5 5 5
4
5 1 9
This input is the same as the first one aside from the value of $B$. Another way
to achieve imbalance $3$ is to set $[s_1,s_2,s_3]=[3,1,6]$.