Barn Tree

题目描述

注意：本题时间限制为 4s，是默认值的两倍。内存限制也为默认值的两倍。 农夫约翰的农场有 $N$ 个谷仓（$2 \leq N \leq 2\cdot 10^5$），编号为 $1 \dots N$。有 $N-1$ 条道路，每条道路连接两个谷仓，并且可以通过若干条道路从任意一个谷仓到达任意另一个谷仓。 目前，第 $j$ 个谷仓有 $h_j$ 捆干草（$1\le h_j\le 10^9$）。 为了让奶牛开心，农夫约翰希望移动干草，使得每个谷仓最终拥有相同数量的干草捆。他可以选择任意一对由道路直接相连的谷仓，并命令工人将第一座谷仓中任意正整数数量、且不超过该谷仓当前干草捆数的干草，从第一座谷仓搬到第二座谷仓。 请确定农夫约翰可以发布的一系列命令，在尽可能少的命令次数内完成任务。保证存在可行的命令序列。

输入格式

第一行输入 $N$。 第二行输入 $h_j$（$j = 1 \dots N$）的空格分隔值。 接下来 $N-1$ 行每行包含两个空格分隔的谷仓编号 $u_i$ 和 $v_i$，表示存在一条连接 $u_i$ 与 $v_i$ 的双向道路。

输出格式

输出最少命令次数，然后输出一段该长度的命令序列，每行一条命令。 每条命令应按三个空格分隔的正整数输出：源谷仓、目标谷仓、以及从源谷仓搬到目标谷仓的干草捆数。 若有多种解，输出任意一种即可。

4
2 1 4 5
1 2
2 3
2 4

3
3 2 1
4 2 2
2 1 1

提示

在该示例中，干草捆总数为十二、谷仓数为四，意味着最终每个谷仓都必须有三捆干草。样例输出中的命令序列可以用如下语言描述： 从谷仓 $3$ 到谷仓 $2$，移动 $1$ 捆。 从谷仓 $4$ 到谷仓 $2$，移动 $2$ 捆。 从谷仓 $2$ 到谷仓 $1$，移动 $1$ 捆。 SCORING: 测试点 2-8 满足 $N\leq 5000$ 测试点 7-10 满足 $v_i=u_i+1$ 测试点 11-16 无额外限制 题目作者：Aryansh Shrivastava

标签: USACO|2022|Silver

来源

USACO|2022|Silver