[USACO22DEC] Barn Tree S

Luogu

IDLGP8900

Time4000ms

Memory512MB

DifficultyP4

贪心USACO2022Special Judge构造

Farmer John 的农场有 $N$ 个牛棚 $(2 \le N \le 2 \times 10^5)$，编号为 $1 \cdots N$。有 $N−1$ 条道路，每条道路连接两个牛棚，并且从任一牛棚均可通过一些道路到达任一其他牛棚。目前，第 $j$ 个牛棚中有 $h_j$ 个干草捆 $(1 \le h_j \le 10^9)$。为使他的奶牛们满意，Farmer John 想移动这些干草，使得每个牛棚都有相同数量的干草捆。他可以选择任何一对由一条道路连接的牛棚，并命令他的农场工人将不超过第一个牛棚中干草捆数量的任意正整数个干草捆从第一个牛棚移动到第二个牛棚。请求出一个 Farmer John 可以发出的命令序列，以尽可能少的命令数完成这一任务。输入保证存在符合要求的命令序列。 ## Input 输入的第一行包含整数 $N$。第二行包含空格分隔的整数 $h_j$，其中 $j=1\cdots N$。最后 $N−1$ 行每行包含两个空格分隔的牛棚编号 $u_i,v_i$，表示有一条双向道路连接 $u_i$ 和 $v_i$。 ## Output 输出命令的最小数量，然后输出该数量的命令序列，每行输出一条命令。每条命令的格式应为三个空格分隔的正整数：出发牛棚，目标牛棚，以及从出发牛棚移动到目标牛棚的干草捆数量。如果有多组解，输出任意一组。 [samples] ## Note ### 样例 1 解释在这个例子中，共有十二个干草捆和四个牛棚，这意味着每个牛棚最后必须有三个干草捆。输出样例中的命令顺序可以用以下的自然语言表述： 1. 从牛棚 $3$ 到牛棚 $2$，移动 $1$ 个干草捆。 2. 从牛棚 $4$ 到牛棚 $2$，移动 $2$ 个干草捆。 3. 从牛棚 $2$ 到牛棚 $1$，移动 $1$ 个干草捆。 ### 测试点性质 - 测试点 $2-8$ 满足 $N \le 5000$。 - 测试点 $7-10$ 满足 $v_i=u_i+1$。 - 测试点 $11-16$ 没有额外限制。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[USACO22DEC] Barn Tree S",
    "description": {
      "content": "Farmer John 的农场有 $N$ 个牛棚 $(2 \\le N \\le 2 \\times 10^5)$，编号为 $1 \\cdots N$。有 $N−1$ 条道路，每条道路连接两个牛棚，并且从任一牛棚均可通过一些道路到达任一其他牛棚。目前，第 $j$ 个牛棚中有 $h_j$ 个干草捆 $(1 \\le h_j \\le 10^9)$。  为使他的奶牛们满意，Farmer John 想移动这些干草",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8900"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 的农场有 $N$ 个牛棚 $(2 \\le N \\le 2 \\times 10^5)$，编号为 $1 \\cdots N$。有 $N−1$ 条道路，每条道路连接两个牛棚，并且从任一牛棚均可通过一些道路到达任一其他牛棚。目前，第 $j$ 个牛棚中有 $h_j$ 个干草捆 $(1 \\le h_j \\le 10^9)$。 \n\n为使他的奶牛们满意，Farmer John 想移动这些干草...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments