#P12640. [UOI 2020] Add edges

    ID: 14189 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2020提交答案Special JudgeUOI(乌克兰)

[UOI 2020] Add edges

题目描述

Given a tree with nn vertices and n1n-1 edges. It is necessary to add exactly mm new edges to this tree. Adding multiple edges or loops is prohibited. If the degree of a certain vertex was tit_i before adding edges, then after adding edges, its degree should not exceed ti+kt_i + k. It should be noted that the degree of a vertex is the number of edges connecting it to other vertices.

In addition, m+n1m+n-1 integers a1,a2,,am+n1a_1, a_2, \dots, a_{m+n-1} are given. After adding edges, it is necessary to assign each edge one of the elements of the array aa so that each element of the array corresponds to exactly one edge. The value aia_i assigned to the edge will denote its weight.

It is necessary to add new edges and assign numbers to the edges in such a way that the sum of the shortest distances between each pair of vertices is maximized. That is, it is necessary to maximize the function dij\sum d_{ij}, where dijd_{ij} is the minimum distance between vertices, for all ii and jj (1i<jn1 \leq i < j \leq n). The minimum distance between vertices is considered to be the sum of the weights of all edges on the simple path between them.

Please note that in this problem, you need to submit not the code, but the actual answers. You also have access to all the tests.

输入格式

There are 55 tests.

The first line of each test contains three integers nn, mm, and kk (1n50001 \leq n \leq 5\,000, 1m2500001 \leq m \leq 250\,000, 1k5001 \leq k \leq 500) - the number of vertices in the tree, the number of edges to be added, and the maximum number of edges that can be added to one vertex.

The second line contains m+n1m+n-1 integers a1,a2,,am+n1a_1, a_2, \dots, a_{m+n-1} (1ai1061 \leq a_i \leq 10^6).

The next n1n-1 lines contain two integers each, viv_i and uiu_i (1vi,uin1 \leq v_i, u_i \leq n) - the numbers of vertices connected by an edge. It is guaranteed that the initially given graph is a tree.

It is guaranteed that it is always possible to add edges in such a way that all the requirements described in the task are met.

输出格式

For each test, output the following:

If you have an answer for this test, output 11, otherwise output 00.

If you have an answer, then in each of the next m+n1m+n-1 lines, output three integers vi,ui,aiv_i, u_i, a_i - the numbers of vertices connected by an edge in the final graph, and its weight.

提示

Let d0d_0 be a certain variable in the test, and dd be the sum of distances in your graph. If d>d0d>d_0, you will receive 2020 points for the test. Otherwise, you will receive as many points for the test as: $$(100^{(d-d_0)/d_0})^5 \cdot 20$$

If ss is the sum of points for all tests, then for the attempt you will receive ss, rounded to the nearest integer.