Cho đồ thị vô hướng dạng cây 𝐺 = (𝑉, 𝐸) gồm 𝑛 đỉnh đánh số từ 1 tới 𝑛. Định nghĩa khoảng cách giữa hai đỉnh 𝑠,𝑡 là số cạnh trên đường đi đơn duy nhất từ 𝑠 tới 𝑡. Độ rộng của cây được định nghĩa bằng tổng khoảng cách giữa mọi cặp đỉnh 𝑠,𝑡 (𝑠 < 𝑡)

Yêu cầu: Xác định độ rộng của cây.

Dữ liệu:

- Dòng 1 chứa số nguyên dương 𝑛 ≤ 10⁵
- 𝑛 − 1 dòng tiếp theo, mỗi dòng chứa chỉ số hai đầu mút của một cạnh cách nhau ít nhất một dấu cách

Kết quả:

Ghi ra một số nguyên duy nhất là độ rộng của cây đã cho