CSES - Tree Distances I | Khoảng cách trên cây I

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

Bạn được cho một cây có \(n\) nút.

Nhiệm vụ của bạn là xác định khoảng cách xa nhất từ mỗi nút đến một nút khác.

Input

  • Dòng đầu tiên chứa một số nguyên \(n:\) số lượng nút. Các nút được đánh số \(1,2,...,n\).
  • Tiếp theo là \(n−1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : có một cạnh nối hai nút \(a\) và \(b\).

Output

  • In ra \(n\) số nguyên: với mỗi nút \(1,2,...,n\), in ra khoảng cách xa nhất đến một nút khác.

Constraints

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

Example

Sample Input

5
1 2
1 3
3 4
3 5

Sample Output
2 3 2 3 3

Bình luận


  • 0
    N7hoatt    11:08 a.m. 17 Tháng 8, 2023

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

    Với mỗi đỉnh, hãy tìm khoảng cách lớn nhất từ đỉnh đó tới một đỉnh khác.

    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

    • In ra \(n\) số nguyên: với mỗi đỉnh \(1,2,3,\dots,n\), in ra khoảng cách lớn nhất tới một đỉnh khác.

    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 3 2 3 3
    Note
    1 phản hồi