Tổng Khoảng Cách Trên Cây Lớn

Buổi 75-76 — Stress Test
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved