Balancing a Tree
플래티넘 II의견: 0
Farmer John has conducted an extensive study of the evolution of different cow
breeds. The result is a rooted tree with \(N\) (\(2\le N\le 10^5\)) nodes labeled
\(1\ldots N\), each node corresponding to a cow breed. For each \(i\in [2,N]\),
the parent of node \(i\) is node \(p_i\) (\(1\le p_i
evolved from breed \(p_i\). A node \(j\) is called an ancestor of node \(i\) if
\(j=p_i\) or \(j\) is an ancestor of \(p_i\).
Every node \(i\) in the tree is associated with a breed having an integer number
of spots \(s_i\). The "imbalance" of the tree is defined to be the maximum of
\(|s_i-s_j|\) over all pairs of nodes \((i,j)\) such that \(j\) is an ancestor of \(i\).
Farmer John doesn't know the exact value of \(s_i\) for each breed, but he knows
lower and upper bounds on these values. Your job is to assign an integer value
of \(s_i \in [l_i,r_i]\) (\(0\le l_i\le r_i\le 10^9\)) to each node such that the
imbalance of the tree is minimized.
Problem credits: Andrew Wang
SCORING
- Test cases 3-4 satisfy \(l_i=r_i\) for all \(i\).
- Test cases 5-6 satisfy \(p_i=i-1\) for all \(i\).
- Test cases 7-16 satisfy no additional constraints.
Within each subtask, the first half of the test cases will satisfy \(B=0\), and
the rest will satisfy \(B=1\).
Problem credits: Andrew Wang
The first line contains \(T\) (\(1\le T\le 10\)), the number of independent test
cases to be solved, and an integer \(B\in \{0,1\}\).
Each test case starts with a line containing \(N\), followed by \(N-1\) integers
\(p_2,p_3,\ldots,p_N\).
The next \(N\) lines each contain two integers \(l_i\) and \(r_i\).
It is guaranteed that the sum of \(N\) over all test cases does not exceed \(10^5\).
For each test case, output one or two lines, depending on the value of \(B\).
The first line for each test case should contain the minimum imbalance.
If \(B=1,\) then print an additional line with \(N\) space-separated integers
\(s_1,s_2,\ldots, s_N\) containing an assignment of spots that achieves the above
imbalance. Any valid assignment will be accepted.
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 103
1
4For 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]\).
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 103
3 1 6
1
6 5 5 5 5
4
5 1 9This 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]\).
평가 및 의견
Balancing a Tree
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Balancing a Tree