CSES - Tree Matching | Cặp ghép trên cây

Xem PDF
Tác giả:
Flower_On_Stone , haidanghutcansa , An09855
Dạng bài
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một cây gồm \(n\) đỉnh.

Một cặp ghép là tập hợp các cạnh mà mỗi đỉnh là đầu mút của tối đa một cạnh. Hãy xác định số lượng cạnh tối đa có trong một cặp ghép.

Input:

  • Dòng đầu tiên gồm một số \(n\): số lượng nút của cây. Các nút được đánh số theo thứ tự \(1, 2, 3, ..., n\).
  • \(n - 1\) dòng tiếp theo, mỗi dòng chứa 2 số \(a\) và \(b\), thể hiện rằng có một cạnh giữa 2 nút này.

Output:

  • Một số nguyên duy nhất\(:\) số cặp tối đa.

Constraints:

  • \(1 ≤ n ≤ 2 \cdot 10 ^ 5\)
  • \(1 ≤ a, b ≤ n\)

Example:

Sample Input:

5
1 2
1 3
3 4
3 5

Sample Output:
2

Note

Có thể lấy cạnh \((1, 2)\) và \((3, 4)\) vào cặp ghép.

Bình luận


  • 0
    N7hoatt    10:56 a.m. 17 Tháng 8, 2023

    Cho một cây gồm \(n\) đỉnh.

    Một cặp ghép là tập hợp các cạnh sao cho mỗi đỉnh là đầu mút của nhiều nhất một cạnh. Hãy tìm số cạnh tối đa có trong một cặp ghép.

    Input

    • Dòng đầu tiên gồm số nguyên \(n\): số đỉnh trong cây. Các đỉnh được đánh số từ \(1,2,\dots,n\).
    • \(n - 1\) dòng sau biểu diễn các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối giữa \(a\) và \(b\).

    Output

    • Một số nguyên: số cạnh tối đa có trong một cặp ghép.

    Constraints

    • \(1 \leq n \leq 2 \times 10^5\).
    • \(1 \leq a, b \leq n\).

    Example

    Test

    Input 
    5
1 2
1 3
3 4
3 5
    Output 
    2
    Note

    Một cặp ghép có thể chọn là \((1,2)\) và \((3,4)\).

      • 1 bình luận nữa