题目描述

题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day2 T4. Додай ребра

这是一个提交答案题。

给定一棵有 $n$ 个顶点和 $n-1$ 条边的树。你需要正好添加 $m$ 条新边到这棵树中。禁止添加重复边或自环。如果在添加边之前某个顶点的度数为 $t_i$，则在添加边之后，该顶点的度数不得超过 $t_i + k$。提醒一下，顶点的度数是指与其相连的边的数量。

此外，还给定 $m+n-1$ 个整数 $a_1, a_2, \dots, a_{m+n-1}$。在添加边之后，你需要将数组 $a$ 中的每个元素与一条边一一对应，使得每个元素恰好对应一条边。对应到边上的值 $a_i$ 表示该边的权重。

你需要添加新边并分配权重，使得每对顶点之间的最短距离之和最大化。即最大化函数 $\sum d_{ij}$，其中 $d_{ij}$ 是顶点 $i$ 和 $j$ 之间的最小距离，对于所有 $1 \leq i < j \leq n$。顶点之间的最小距离定义为它们之间简单路径上所有边的权重之和。

请注意，本题不需要提交代码，只需提交答案。你还可以从「文件」下载所有测试数据。

输入格式

共给定 $5$ 组输入数据。

每组输入数据的第一行包含三个整数 $n, m, k$ $(1 \leq n \leq 5000, 1 \leq m \leq 250000, 1 \leq k \leq 500)$，分别表示树的顶点数量、需要添加的边数以及每个顶点最多可以添加的边数。

第二行包含 $m+n-1$ 个整数 $a_1, a_2, \dots, a_{m+n-1}$ $(1 \leq a_i \leq 10^{6})$。

接下来的 $n-1$ 行，每行包含两个整数 $v_i$ 和 $u_i$ $(1 \leq v_i, u_i \leq n)$，表示初始树中顶点之间的边。保证初始图是一棵树。

保证总是可以添加边，使得满足题目中描述的所有要求。

输出格式

对于每组输入数据，输出以下内容：

如果你有该组数据的答案，输出 $1$；否则输出 $0$。

如果你有答案，则在接下来的 $m+n-1$ 行中，每行输出三个整数 $v_i, u_i, a_i$，表示最终图中边的两个顶点编号及其权重。

数据范围与提示

设 $d_0$ 为测试中的某个基准值，$d$ 为你的图中距离之和。如果 $d > d_0$，你将获得该测试的 $20$ 分。否则，你将获得的分数为：

如果 $s$ 是所有测试点的分数总和，则你的提交将获得 $s$ 的四舍五入到最近整数的值。