Tính tổng khoảng cách trong cây

Xem dưới dạng PDF

Gửi bài giải

Điểm: 30
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Kiểu bài tập

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

Không có ý kiến tại thời điểm này.