P9077 [PA 2018] Poddrzewo

**This problem is translated from [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/) Round 1 [Poddrzewo](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/pod/).** You are given a sequence $a$ of length $n$. Construct an undirected tree with $k$ nodes, numbered $1 \cdots k$. The degree of node $i$ in this tree must be $a_i$. A solution may not exist. You are allowed to perform the following operations to make it solvable: 1. Modify the $i$-th number in the sequence. 1. Delete the $i$-th number from the sequence. 1. Swap the $i$-th and $j$-th numbers in the sequence. It can be proven that after a finite number of operations, a solution will always exist. Your task is to **minimize the number of times operation 1 is used**.

The first line contains an integer $n$, the length of the sequence $a$. The second line contains $n$ integers. The $i$-th integer is $a_i$.

The first line contains an integer $x$, the minimum number of times operation 1 is used. The second line contains an integer $k\ (2 \le k \le n)$, the number of nodes in the tree you construct. In the next $k - 1$ lines, each line contains two integers $u, v\ (1 \le u, v \le k)$, indicating an edge between nodes $u$ and $v$. If there are multiple solutions, output any one.

#### Explanation for Sample 1 We can delete the $3$-rd number and then change the order of the elements. The final sequence becomes $(3,2,1,1,1)$. This is a schematic diagram of the constructed tree:  ------------ #### Explanation for Sample 2 We can modify the $3$-rd number, and the final sequence becomes $(1,2,1)$. It can be proven that operation 1 must be used at least $1$ time. This is a schematic diagram of the constructed tree:  ------------ #### Constraints **This problem uses bundled testdata.** For $100\%$ of the testdata: - $2 \le n \le 10^6$. - $1 \le a_i \le n - 1$. It is guaranteed that there exists at least one subtask where the minimum value of the number of times operation 1 is used is $0$. Translated by ChatGPT 5