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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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


  • -5
    xthabao1    11:03 p.m. 2 Tháng 9, 2023

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


    • -2
      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)\).