Farmer John's farm has N barns (2≤N≤2⋅105) numbered 1…N. There are N−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 jth barn has hj hay bales (1≤hj≤109).

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.

#5407 upload 17 done 9 how_to_reg 5 auto_awesome スペシャルジャッジ

병영 (Barn Tree) timer 4s memory 512MB

#5407
スペシャルジャッジ

병영 (Barn Tree) 4s 512MB