CSES - Tree Distances II | Khoảng cách trên cây II
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một cây gồm \(n\) đỉnh.
Nhiệm vụ của bạn là với mỗi nút, hãy tìm tổng khoảng cách từ nó tới tất cả các nút khác.
Input
- Dòng đầu chứa một số nguyên \(n:\) số lượng nút. Các nút được đánh số \(1,2,... ,n\).
- Sau đó 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 nút \(a\) và \(b\).
Output
- In ra \(n\) số nguyên\(:\) tổng khoảng cách từ các nút \(1,2,3,\dots,n\).
Constraints
- \(1 ≤ n ≤ 2⋅10^5\)
- \(1 ≤ a,b ≤ n\)
Example
Sample Input
5
1 2
1 3
3 4
3 5
Sample Output
6 9 5 8 8
Note
Trong Test ví dụ:
Với nút \(1\)
- Khoảng cách từ nút \(1\) tới nút \(2\) là \(1\),
- từ nút \(1\) tới nút \(3\) là \(1\),
- từ nút \(1\) tới nút \(4\) là \(2\),
- từ nút \(1\) tới nút \(5\) là \(2\)
\(\Rightarrow\) Tổng khoảng cách từ nút \(1\) tới các nút còn lại là \(1 + 1 + 2 + 2 = 6\), vậy nên ta in ra \(6\).
Tương tự với các đỉnh còn lại
Bình luận
Cho một cây gồm \(n\) đỉnh.
Với mỗi đỉnh, hãy tìm tổng khoảng cách từ đỉnh đó tới tất cả đỉnh khác.
Input
Output
Constraints
Example
Test
Input
Output
Note