**Definitions:**
- Let $ n $ be the number of cities, labeled $ 1, 2, \dots, n $, where city $ 1 $ is the capital.
- Let $ t $ be the maximum distance from the capital to any city.
- Let $ k $ be the number of dead-end cities (degree-1 nodes excluding the capital).
- Let $ a_i $ be the number of cities at distance $ i $ from the capital, for $ i = 1, 2, \dots, t $, with $ \sum_{i=1}^t a_i = n - 1 $.
**Constraints:**
1. The graph must be a tree with $ n $ nodes and $ n - 1 $ edges.
2. The distance from node $ 1 $ (capital) to the farthest node is exactly $ t $.
3. The number of nodes at distance $ i $ from the capital is exactly $ a_i $, for $ i = 1, \dots, t $.
4. Exactly $ k $ nodes (excluding the capital) have degree 1 (dead-ends).
5. The capital (node 1) may have any degree, and is not counted in $ k $.
**Objective:**
Construct such a tree, or determine that it is impossible.
---
**Necessary Conditions for Feasibility:**
Let $ d_i $ denote the number of nodes at distance $ i $, so $ d_i = a_i $.
Let $ D = \sum_{i=1}^t d_i = n - 1 $.
Let $ L $ be the total number of leaves (degree-1 nodes) in the tree, excluding the capital.
Then $ L = k $.
In any tree:
- Sum of degrees = $ 2(n - 1) $.
- Let $ \delta_1 $ be the number of degree-1 nodes (leaves), $ \delta_2 $ degree-2, etc.
- Then $ \sum_{v} \deg(v) = 2(n - 1) $.
- Let $ \ell = \text{number of leaves (degree-1 nodes)} = k $ (excluding capital), but the capital may also be a leaf.
Let $ c = \deg(1) $ be the degree of the capital.
Then total leaves in the tree = $ k + \mathbf{1}_{\deg(1)=1} $.
But note: the problem says **“among all cities except the capital there should be exactly $ k $ cities with exactly one road”**, so:
> The capital is **never** counted in $ k $, regardless of its degree.
So total leaves in the tree = $ k + \delta $, where $ \delta = 1 $ if $ \deg(1) = 1 $, else $ 0 $.
But we don’t know $ \deg(1) $ yet.
We can compute the number of leaves from the tree structure.
Let’s denote:
- $ L = k $: number of degree-1 nodes **not** including the capital.
- Let $ m = \sum_{i=1}^t d_i = n - 1 $: total non-capital nodes.
Let $ S = \sum_{v \ne 1} \deg(v) $.
Then total degree sum: $ \deg(1) + S = 2(n - 1) \Rightarrow S = 2(n - 1) - \deg(1) $.
But $ S = \sum_{v \ne 1} \deg(v) $.
Also, among the $ n - 1 $ non-capital nodes:
- $ k $ of them have degree 1 (dead-ends).
- The remaining $ n - 1 - k $ have degree $ \geq 2 $.
So:
$$
S \geq k \cdot 1 + (n - 1 - k) \cdot 2 = k + 2(n - 1 - k) = 2(n - 1) - k
$$
But we also have:
$$
S = 2(n - 1) - \deg(1)
$$
So:
$$
2(n - 1) - \deg(1) \geq 2(n - 1) - k \Rightarrow -\deg(1) \geq -k \Rightarrow \deg(1) \leq k
$$
Also, since $ \deg(1) \geq 1 $ (tree connected, capital must connect to at least one child), we have:
> $ 1 \leq \deg(1) \leq k $
Moreover, since the farthest node is at distance $ t $, there must be **at least one** node at distance $ t $, so $ a_t \geq 1 $.
Also, for the tree to have a path of length $ t $, we must have a chain of $ t $ edges from the capital, so:
> $ a_1 \geq 1 $, $ a_2 \geq 1 $, ..., $ a_t \geq 1 $ — **not necessarily**; only that the *maximum* distance is $ t $, so $ a_t \geq 1 $, but lower levels can be zero? Wait — the input says: “the sequence of $ t $ integers $ a_1, a_2, \dots, a_t $”, and “$ a_i $ equals the number of cities which should be at distance $ i $”, and sum is $ n - 1 $. So if $ a_i = 0 $ for some $ i < t $, then there is a gap — **this is not allowed**, because the distance from the capital to a node at level $ t $ must pass through level $ t-1 $, so if $ a_{t-1} = 0 $, then no node can be at distance $ t $.
Therefore, **we must have $ a_i \geq 1 $ for all $ i = 1, 2, \dots, t $**.
Otherwise, impossible.
So **necessary condition 1**: $ a_i \geq 1 $ for all $ i \in \{1, 2, \dots, t\} $.
Now, to construct the tree:
We will build the tree level by level (BFS-style from the capital).
- Level 0: node 1 (capital).
- Level 1: $ a_1 $ nodes, all connected to node 1.
- Level 2: $ a_2 $ nodes, each connected to some node in level 1.
- ...
- Level $ t $: $ a_t $ nodes, connected to level $ t-1 $.
We must assign parent-child relationships so that:
- The number of dead-ends (degree-1 nodes among non-capital nodes) is exactly $ k $.
- The total number of edges is $ n - 1 $.
Let’s denote:
- $ N_i = a_i $: number of nodes at level $ i $.
- The nodes at level $ i $ are children of nodes at level $ i - 1 $.
Let $ p_i $ be the number of parent nodes at level $ i - 1 $ that have children at level $ i $.
Each node at level $ i $ has exactly one parent (in a tree).
So total number of edges from level $ i - 1 $ to level $ i $ is $ N_i $.
Each parent node at level $ i - 1 $ can have multiple children.
Let $ c_j $ be the number of children of node $ j $ at level $ i - 1 $.
Then the number of children of all nodes at level $ i - 1 $ is $ N_i $.
The degree of a node at level $ i - 1 $ is:
- If $ i - 1 = 0 $ (capital): degree = number of children (since no parent).
- If $ i - 1 \geq 1 $: degree = 1 (to parent) + number of children.
A node is a dead-end if its degree is 1.
So:
- A node at level $ i $ (where $ i \geq 1 $) is a dead-end if and only if it has **zero** children.
So the number of dead-end nodes = total number of nodes at levels $ 1 $ to $ t $ that have no children.
Let $ D $ be the total number of dead-ends = $ k $.
We can compute:
- Total nodes at levels $ 1 $ to $ t $: $ \sum_{i=1}^t a_i = n - 1 $.
- Number of nodes that have children: these are the non-dead-end non-capital nodes.
Let $ x_i $ = number of nodes at level $ i $ that have at least one child (i.e., are not dead-ends).
Then the number of dead-ends = $ (n - 1) - \sum_{i=1}^{t-1} x_i $, because only nodes at levels $ 1 $ to $ t-1 $ can have children (nodes at level $ t $ cannot have children, since $ t $ is max distance).
So:
> $ k = (n - 1) - \sum_{i=1}^{t-1} x_i $
Thus:
> $ \sum_{i=1}^{t-1} x_i = n - 1 - k $
But also, the number of edges from level $ i $ to $ i+1 $ is $ a_{i+1} $, and these must be distributed among the $ x_i $ nodes at level $ i $ that have children.
So the $ a_{i+1} $ children at level $ i+1 $ are assigned to the $ x_i $ parent nodes at level $ i $, each of which must have at least 1 child (since they are non-dead-ends).
So for each level $ i = 1 $ to $ t - 1 $, we have:
- $ x_i $ nodes, each with at least 1 child → total children ≥ $ x_i $
- But total children = $ a_{i+1} $
So: $ a_{i+1} \geq x_i $
Also, total number of non-dead-end nodes from level 1 to $ t-1 $: $ \sum_{i=1}^{t-1} x_i = n - 1 - k $
And $ x_i \leq a_i $, obviously.
So we can try to **minimize** the number of non-dead-end nodes: set $ x_i = \max(1, a_{i+1}) $? No.
Actually, to satisfy $ a_{i+1} \geq x_i $ and $ \sum x_i = n - 1 - k $, and $ x_i \leq a_i $, and $ x_i \geq 1 $ if $ a_{i+1} \geq 1 $ (which it is, since $ a_{i+1} \geq 1 $ for $ i+1 \leq t $).
We need to check if there exist integers $ x_1, \dots, x_{t-1} $ such that:
- $ 1 \leq x_i \leq a_i $ for each $ i = 1, \dots, t-1 $
- $ \sum_{i=1}^{t-1} x_i = n - 1 - k $
- $ a_{i+1} \geq x_i $ for each $ i = 1, \dots, t-1 $
This is a necessary and sufficient condition.
Also, since the capital (level 0) has degree $ a_1 $, and we require $ \deg(1) \leq k $, as shown earlier, so:
> $ a_1 \leq k $
Because $ \deg(1) = a_1 $, and $ \deg(1) \leq k $.
So **necessary conditions**:
1. $ a_i \geq 1 $ for all $ i = 1, \dots, t $
2. $ a_1 \leq k $
3. $ \sum_{i=1}^{t-1} x_i = n - 1 - k $, with $ \max(1, a_{i+1} - \text{some slack}) \leq x_i \leq \min(a_i, a_{i+1}) $? Wait.
Actually, from above:
We need:
- $ x_i \leq a_i $ (can't have more non-dead-end nodes than exist at level $ i $)
- $ x_i \leq a_{i+1} $ (can't have more parent nodes than children to assign)
- $ x_i \geq 1 $ (since $ a_{i+1} \geq 1 $, and we must have at least one parent to assign them to)
- $ \sum x_i = n - 1 - k $
But also, since each $ x_i \geq 1 $, we must have:
> $ t - 1 \leq n - 1 - k \Rightarrow k \leq n - t $
Also, since $ x_i \leq a_{i+1} $, then:
> $ \sum_{i=1}^{t-1} x_i \leq \sum_{i=1}^{t-1} a_{i+1} = \sum_{j=2}^t a_j = (n - 1) - a_1 $
So:
> $ n - 1 - k \leq (n - 1) - a_1 \Rightarrow -k \leq -a_1 \Rightarrow a_1 \leq k $
Which we already have.
Similarly, since $ x_i \geq 1 $, we have:
> $ n - 1 - k \geq t - 1 \Rightarrow k \leq n - t $
So **additional necessary conditions**:
4. $ k \leq n - t $
And from above, we also have:
> $ \sum_{i=1}^{t-1} x_i = n - 1 - k $, and $ x_i \in [1, \min(a_i, a_{i+1})] $
So the minimal possible sum of $ x_i $ is $ t - 1 $, maximal is $ \sum_{i=1}^{t-1} \min(a_i, a_{i+1}) $
Thus, we require:
> $ t - 1 \leq n - 1 - k \leq \sum_{i=1}^{t-1} \min(a_i, a_{i+1}) $
But since $ a_{i+1} \geq 1 $ and $ a_i \geq 1 $, and we can always choose $ x_i = \min(a_i, a_{i+1}) $ if we want to maximize, but we need exact sum.
Actually, we can construct $ x_i $ greedily:
We need to choose $ x_i \in [1, \min(a_i, a_{i+1})] $ such that $ \sum x_i = n - 1 - k $
We can set:
- Start with $ x_i = 1 $ for all $ i = 1, \dots, t - 1 $ → sum = $ t - 1 $
- We have a deficit: $ \Delta = (n - 1 - k) - (t - 1) = n - k - t $
- We can increase some $ x_i $ up to $ \min(a_i, a_{i+1}) - 1 $, as long as $ \Delta \geq 0 $
So if $ n - k - t < 0 $, impossible.
Otherwise, we need to distribute $ \Delta $ extra units over the $ t - 1 $ levels, with maximum increase per level $ \delta_i = \min(a_i, a_{i+1}) - 1 $
So if $ \sum_{i=1}^{t-1} \delta_i \geq \Delta $, then possible.
Thus, **final necessary conditions**:
1. $ a_i \geq 1 $ for all $ i = 1, \dots, t $
2. $ a_1 \leq k $
3. $ k \leq n - t $
4. $ \Delta = n - k - t \geq 0 $
5. $ \sum_{i=1}^{t-1} \left( \min(a_i, a_{i+1}) - 1 \right) \geq \Delta $
If all hold, then we can construct.
**Construction Algorithm:**
1. Assign node IDs: capital = 1.
2. Assign nodes to levels:
- Level 0: node 1
- Level 1: nodes $ 2 $ to $ 1 + a_1 $
- Level 2: nodes $ 2 + a_1 $ to $ 1 + a_1 + a_2 $
- ...
- Level $ i $: nodes from $ 1 + \sum_{j=1}^{i-1} a_j + 1 $ to $ 1 + \sum_{j=1}^{i} a_j $
Let $ \text{start}_i = 1 + \sum_{j=1}^{i-1} a_j $, then level $ i $ has nodes $ \text{start}_i + 1 $ to $ \text{start}_i + a_i $
3. For each level $ i = 1 $ to $ t - 1 $:
- We need to assign $ x_i $ parent nodes from level $ i $ to parent the $ a_{i+1} $ children in level $ i+1 $
- We choose $ x_i $ as follows:
- Start with $ x_i = 1 $
- We have a remaining budget $ \Delta = n - k - t $
- For each level $ i $, we can increase $ x_i $ up to $ \min(a_i, a_{i+1}) $, but we want to distribute the extra $ \Delta $
So:
- For $ i = 1 $ to $ t - 1 $:
- Let $ \text{max\_inc}_i = \min(a_i, a_{i+1}) - 1 $
- Let $ \text{inc}_i = \min(\Delta, \text{max\_inc}_i) $
- Set $ x_i = 1 + \text{inc}_i $
- $ \Delta \gets \Delta - \text{inc}_i $
(This greedy assignment works since the max sum of increases is sufficient by condition 5.)
4. Now assign children:
- For level $ i = 1 $ to $ t - 1 $:
- Take the first $ x_i $ nodes in level $ i $ as parents (they will have children)
- The remaining $ a_i - x_i $ nodes in level $ i $ are dead-ends (degree 1) — we don’t assign children to them.
- Distribute the $ a_{i+1} $ children in level $ i+1 $ among the $ x_i $ parents.
To do this, assign children in round-robin fashion to ensure no parent gets too many (but any assignment is fine).
Since $ a_{i+1} \geq x_i $, we can assign at least one child to each parent.
We can assign:
- Each of the $ x_i $ parents gets at least 1 child.
- Remaining $ a_{i+1} - x_i $ children can be distributed arbitrarily (e.g., to the first parent, or spread out).
We’ll assign in order: first child to first parent, second to second, ..., then cycle.
5. Output edges: for each child in level $ i+1 $, connect it to its assigned parent in level $ i $.
6. Verify: total dead-ends = nodes at level $ t $ (all dead-ends, since no children) + nodes at levels $ 1 $ to $ t-1 $ that have no children = $ a_t + \sum_{i=1}^{t-1} (a_i - x_i) $
= $ \sum_{i=1}^t a_i - \sum_{i=1}^{t-1} x_i = (n - 1) - (n - 1 - k) = k $ → correct.
7. The farthest node is at level $ t $, so distance = $ t $, as required.
8. The capital has degree $ a_1 \leq k $, as required.
---
**Summary of Algorithm:**
**Input:** $ n, t, k $, array $ a[1..t] $
**Check conditions:**
- If any $ a_i = 0 $ for $ i \in [1, t] $ → return -1
- If $ a_1 > k $ → return -1
- If $ k > n - t $ → return -1
- Let $ \Delta = n - k - t $
- If $ \Delta < 0 $ → return -1
- Let $ \text{max\_extra} = \sum_{i=1}^{t-1} \left( \min(a_i, a_{i+1}) - 1 \right) $
- If $ \text{max\_extra} < \Delta $ → return -1
**Construct:**
- Let $ \text{nodes}[i] $ = list of node IDs at level $ i $
- Compute prefix sums to assign node IDs.
- Initialize $ x_i = 1 $ for $ i = 1 $ to $ t-1 $
- $ \text{rem} = \Delta $
- For $ i = 1 $ to $ t-1 $:
- $ \text{inc} = \min(\text{rem}, \min(a_i, a_{i+1}) - 1) $
- $ x_i \gets x_i + \text{inc} $
- $ \text{rem} \gets \text{rem} - \text{inc} $
- For each level $ i = 1 $ to $ t - 1 $:
- Let $ \text{parents} = \text{nodes}[i][0 : x_i] $ (first $ x_i $ nodes)
- Let $ \text{children} = \text{nodes}[i+1] $ (all $ a_{i+1} $ nodes)
- For $ j = 0 $ to $ a_{i+1} - 1 $:
- parent_index = $ j \mod x_i $
- Output edge: $ \text{parents}[parent_index] $ — $ \text{children}[j] $
- Output $ n - 1 $ edges.
**Output:**
- First line: $ n $
- Next $ n - 1 $ lines: edges
If any condition fails, output -1.