Cho một cây gồm \(n\) đỉnh. Nhiệm vụ của bạn là với mỗi đỉnh tính tổng khoảng cách từ đỉnh đó đến tất cả các đỉnh còn lại.
Đầu vào
- Dòng đầu tiên chứa một số nguyên \(n\): số đỉnh của cây. Các đỉnh được đánh số từ 1 đến n.
- Tiếp theo có \(n - 1\) dòng, mỗi dòng gồm hai số nguyên \(a\) và \(b\), cho biết có một cạnh nối giữa đỉnh \(a\) và đỉnh \(b\).
Đầu ra
- In ra \(n\) số nguyên: với mỗi đỉnh \(1, 2, …, n\), in ra tổng các khoảng cách từ đỉnh đó đến tất cả các đỉnh còn lại.
Ràng buộc
- \(1 \le n \le 2\cdot10^5\)
- \(1 \le a, b \le n\)
Input 1
5
1 2
1 3
3 4
3 5
Output 1
6 9 5 8 8
Nhận xét