Gốc đối xứng hoàn hảo

Điểm: 8,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một cây gồm $n$ đỉnh. Hãy tìm một đỉnh để làm gốc sao cho điều kiện sau được thỏa mãn:

Với mọi cặp đỉnh $v_{1}, v_{2}$ , nếu $dist (root, v_{1}) = dist (root, v_{2})$ thì $\deg (v_{1}) = \deg (v_{2})$ .

Trong đó $\deg (v)$ là số đỉnh kề với $v$ trong cây (bậc của $v$ ), và $dist (u, v)$ là số cạnh trên đường đi ngắn nhất giữa $u$ và $v$ .

Hãy chỉ ra một đỉnh gốc thỏa mãn nếu tồn tại; nếu có nhiều đáp án, in ra một đáp án bất kỳ. Nếu không tồn tại đỉnh gốc nào thỏa mãn, in ra $- 1$ .

Dòng đầu tiên chứa một số nguyên $n$ — số đỉnh.
Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số nguyên $v_{i}, u_{i}$ ( $1 \leq v_{i} < u_{i} \leq n$ ) — mô tả một cạnh giữa $v_{i}$ và $u_{i}$ .

Dữ liệu đảm bảo đồ thị tạo thành một cây.

In ra một số nguyên — chỉ số của một đỉnh gốc thỏa mãn, hoặc $- 1$ nếu không tồn tại.

Input	Output	Giải thích
6 1 3 2 3 3 4 4 5 4 6	-1	Không tồn tại đỉnh gốc nào thỏa mãn.
7 1 2 2 3 3 4 4 5 3 6 6 7	5	Các đỉnh $1, 3, 5, 7$ đều là đáp án hợp lệ. Với gốc $= 5$ : ở độ sâu $0$ chỉ có đỉnh $5$ (bậc $1$ ), độ sâu $1$ chỉ có đỉnh $4$ (bậc $2$ ), độ sâu $2$ chỉ có đỉnh $3$ (bậc $3$ ), độ sâu $3$ có ${2, 6}$ đều bậc $2$ , độ sâu $4$ có ${1, 7}$ đều bậc $1$ .

Bình luận

Không có bình luận tại thời điểm này.