P7026: 谷仓树
传统题
4.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
Farmer John
的农场有 N 个牛棚（2≤N≤2×10
^5
），编号为 1…N。有N−1
条道路，每条道路连接两个牛棚，并且从任一牛棚均可通过一些道路到达任一其他牛棚。目前，第 j 个牛棚中有 hj 个干草捆（1≤hj≤10^9
）。
为使他的奶牛们满意，Farmer John
想移动这些干草，使得每个牛棚都有相同数量的干草捆。他可以选择任何一对由一条道路连接的牛棚，并命令他的农场工人将不超过第一个牛棚中干草捆数量的任意正整数个干草捆从第一个牛棚移动到第二个牛棚。
请求出一个 Farmer John
可以发出的命令序列，以尽可能少的命令数完成这一任务。输入保证存在符合要求的命令序列。
【
输入格式】
（从终端 /
标准输入读入）：
输入的第一行包含整数 N
。
第二行包含空格分隔的整数 hj
，其中 j=1…N
。
最后 N−1
行每行包含两个空格分隔的牛棚编号 ui vi，表示有一条双向道路连接 ui
和 vi。
【
输出格式】
（输出至终端 /
标准输出）：
输出命令的最小数量，然后输出该数量的命令序列，每行输出一条命令。
每条命令的格式应为三个空格分隔的正整数：出发牛棚，目标牛棚，以及从出发牛棚移动到目标牛棚的干草捆数量。
如果有多组解，输出任意一组。
【
输入样例】
：
4
2 1 4 5
1 2
2 3
2 4
【
输出样例】
：
3
3 2 1
4 2 2
2 1 1
【样例说明】
在这个例子中，共有十二个干草捆和四个牛棚，这意味着每个牛棚最后必须有三个干草捆。输出样例中的命令顺序可以用以下的自然语言表述：
1.从牛棚 3
到牛棚 2
，移动 1
个干草捆。
2.从牛棚 4
到牛棚 2
，移动 2
个干草捆。
3.从牛棚 2
到牛棚 1
，移动 1
个干草捆。
【
测试点性质】
测试点 2-8
满足 N≤5000。
测试点 7-10
满足 vi=ui+1。
测试点 11-16
没有额外限制。