#PU1254. USACO 2022 December Contest, Silver — Problem 1. Barn Tree

    ID: 1204 传统题 4000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:dec22来源:usaco.orgscoring:equal_test_cases广搜最短路

USACO 2022 December Contest, Silver — Problem 1. Barn Tree

USACO 2022 December Contest, Silver — Problem 1. Barn Tree

题目描述

Note: the time limit for this problem is 4s, two times the default. The memory limit is also twice the default. Farmer John's farm has NN barns (2≤N≤2⋅1052 \leq N \leq 2\cdot 10^5) numbered 1…N1 \dots N. There are N−1N-1 roads, where each road connects two barns and it is possible to get from any barn to any other barn via some sequence of roads. Currently, the jjth barn has hjh_j hay bales (1≤hj≤1091\le h_j\le 10^9). To please his cows, Farmer John would like to move the hay such that each barn has an equal number of bales. He can select any pair of barns connected by a road and order his farmhands to move any positive integer number of bales less than or equal to the number of bales currently at the first barn from the first barn to the second. Please determine a sequence of orders Farmer John can issue to complete the task in the minimum possible number of orders. It is guaranteed that a sequence of orders exists.

输入格式

The first line of input contains the value of N.N. The second line of input contains the space-separated values of hjh_j for j=1…Nj = 1 \dots N. The final N−1N-1 lines of input each contain two space-separated barn numbers ui viu_i \ v_i, indicating that there is a bidirectional road connecting uiu_i and viv_i.

输出格式

(见题面原文)

数据范围

Test cases 2-8 satisfy N≤5000N\leq 5000 Test cases 7-10 satisfy vi=ui+1v_i=u_i+1 Test cases 11-16 satisfy no additional constraints Problem credits: Aryansh Shrivastava

样例

样例 1

4
2 1 4 5
1 2
2 3
2 4
3
3 2 1
4 2 2
2 1 1
In this example, there are a total of twelve hay bales and four barns, meaning
each barn must have three hay bales at the end. The sequence of orders in the