CSES - Prüfer Code | Mã Prüfer
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Mã Prüfer của một cây gồm \(n\) đỉnh là một dãy gồm \(n-2\) số nguyên chỉ xác định duy nhất một cấu trúc của cây.
Đoạn mã được hình thành như sau: Khi vẫn còn ít nhất ba đỉnh trên cây, tìm đỉnh lá có chỉ số nhỏ nhất, thêm chỉ số của đỉnh kề duy nhất của nó vào đoạn mã, và bỏ đỉnh lá đó ra khỏi cây.
Cho một mã Prüfer của một cây, nhiệm vụ của bạn là xây dựng lại cây ban đầu.
Input
- Dòng đầu tiên chứa một số nguyên \(n\) là số lượng đỉnh của cây. Các đỉnh được đánh số từ \(1\) đến \(n\).
- Dòng thứ hai chứa \(n-2\) số nguyên là mã Prüfer.
Output
- In ra \(n-1\) dòng mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) có ý nghĩa là có một cạnh nối giữa hai đỉnh \(a\) và \(b\). Bạn có thể in các cạnh theo thứ tự bất kỳ.
Constraints
- \(3 \le n \le 2 \times 10^5\)
- \(1 \le a, b \le n\)
Example
Sample input
5
2 2 4
Sample output
1 2
2 3
2 4
4 5
Bình luận
CSES - Prüfer Code | Mã Prüfer
Mã Prüfer của một cây \(n\) đỉnh là một dãy gồm \(n-2\) số nguyên xác định duy nhất một cấu trúc của cây.
Mã được xây dựng như sau: Trong khi cây còn ít nhất ba đỉnh, tìm một đỉnh lá với chỉ số nhỏ nhất, thêm chỉ số của đỉnh kề duy nhất của nó vào mã, và loại bỏ đỉnh lá đó khỏi cây.
Bạn được cho mã Prüfer của một cây, nhiệm vụ của bạn là xây dựng cây ban đầu.
Input
Output
Example
Input
Output