CSES - Tree Distances I | Khoảng cách trên cây I
Xem PDF
Đ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
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
Output
Constraints
Example
Test
Input
Output
Note