Ghép cạnh trên cây

Điểm: 1,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

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một cây có $n$ đỉnh. Hãy tìm matching lớn nhất trên cây — tức là tập hợp các cạnh sao cho mỗi đỉnh thuộc vào tối đa một cạnh trong tập.

Dòng đầu chứa số nguyên $n$ : số đỉnh (đánh số từ $1$ đến $n$ ).

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ : một cạnh của cây.

In một số nguyên: số cạnh trong matching lớn nhất.

Input	Output	Giải thích
5 1 2 1 3 3 4 3 5	2	Chọn cạnh (1,2) và (3,4). Không thể chọn thêm cạnh nào khác vì đỉnh 1, 2, 3, 4 đã bị dùng.
2 1 2	1	Chỉ có một cạnh, chọn nó.

Bình luận

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