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,\ldots,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\)
Constraints
- \(1 \leq n \leq 2\cdot 10^5\)
- \(1 \leq a,b \leq n\)
Output
- In ra \(n\) số nguyên: tổng khoảng cách từ các nút \(1,2,3,\ldots,n\)
Example
Test 1
Input
5
1 2
1 3
3 4
3 5Output
6 9 5 8 8Note
Trong test ví dụ:
Với nút \(1\):
- Khoảng cách từ nút \(1\) tới nút \(2\) là \(1\)
- Khoảng cách từ nút \(1\) tới nút \(3\) là \(1\)
- Khoảng cách từ nút \(1\) tới nút \(4\) là \(2\)
- Khoảng cách 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 (2)