#PU1235. USACO 2022 US Open Contest, Gold — Problem 3. Balancing a Tree

    ID: 1632 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:open22来源:usaco.orgscoring:equal_test_cases动态规划贪心

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 NN (2≤N≤1052\le N\le 10^5) nodes labeled 1…N1\ldots N, each node corresponding to a cow breed. For each i∈[2,N]i\in [2,N], the parent of node ii is node pip_i (1≤pi<i1\le p_i<i), meaning that breed ii evolved from breed pip_i. A node jj is called an ancestor of node ii if j=pij=p_i or jj is an ancestor of pip_i. Every node ii in the tree is associated with a breed having an integer number of spots sis_i. The "imbalance" of the tree is defined to be the maximum of ∣si−sj∣|s_i-s_j| over all pairs of nodes (i,j)(i,j) such that jj is an ancestor of ii. Farmer John doesn't know the exact value of sis_i for each breed, but he knows lower and upper bounds on these values. Your job is to assign an integer value of si∈[li,ri]s_i \in [l_i,r_i] (0≤li≤ri≤1090\le l_i\le r_i\le 10^9) to each node such that the imbalance of the tree is minimized.

输入格式

The first line contains TT (1≤T≤101\le T\le 10), the number of independent test cases to be solved, and an integer B∈{0,1}B\in \{0,1\}. Each test case starts with a line containing NN, followed by N−1N-1 integers p2,p3,…,pNp_2,p_3,\ldots,p_N. The next NN lines each contain two integers lil_i and rir_i. It is guaranteed that the sum of NN over all test cases does not exceed 10510^5.

输出格式

For each test case, output one or two lines, depending on the value of BB. The first line for each test case should contain the minimum imbalance. If B=1,B=1, then print an additional line with NN space-separated integers s1,s2,…,sNs_1,s_2,\ldots, s_N containing an assignment of spots that achieves the above imbalance. Any valid assignment will be accepted.

数据范围

Test cases 3-4 satisfy li=ril_i=r_i for all ii. Test cases 5-6 satisfy pi=i−1p_i=i-1 for all ii. Test cases 7-16 satisfy no additional constraints. Within each subtask, the first half of the test cases will satisfy B=0B=0, and the rest will satisfy B=1B=1. 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]$.