Tổng Khoảng Cách Trên Cây Lớn
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một cây gồm $N$ đỉnh. Với mỗi đỉnh $u$, gọi $D(u) = \sum_{v=1}^{N} \text{dist}(u, v)$ là tổng khoảng cách (số cạnh) từ $u$ đến tất cả các đỉnh trong cây. Hãy tìm giá trị nhỏ nhất và lớn nhất của $D(u)$ trên tất cả các đỉnh $u \in {1, \dots, N}$.
Chú ý: Kết quả có thể vượt quá $2^{31}-1$ và cây có thể có dạng đường thẳng dài $2 \times 10^5$ đỉnh.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 2 \times 10^5$).
- $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$).
Dữ liệu ra
- In ra hai số nguyên trên một dòng: $\min D(u)$ và $\max D(u)$.
Ví dụ
| Input | Output |
|---|---|
| 4 1 2 2 3 3 4 |
4 6 |
Giới hạn
- $1 \le N \le 2 \times 10^5$
Community Discussion