Tổng Hai Đường Kính Khi Cắt Cạnh
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh ($N \ge 2$) đánh số từ $1$ đến $N$ và $N - 1$ cạnh vô hướng có độ dài $1$. Với mỗi cạnh thứ $i$ ($1 \le i \le N - 1$) theo thứ tự nhập, nếu ta xóa cạnh đó đi thì cây ban đầu sẽ tách thành hai cây rời nhau $T_1$ và $T_2$. Hãy tính tổng đường kính của hai cây tạo thành: $\text{diam}(T_1) + \text{diam}(T_2)$.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$.
Dữ liệu ra
- Gồm $N - 1$ số nguyên trên một dòng, số thứ $i$ là tổng đường kính hai cây khi xóa cạnh thứ $i$.
Ví dụ
| Input | Output |
|---|---|
| 5 1 2 2 3 3 4 3 5 |
2 3 3 3 |
Giới hạn
- $2 \le N \le 10^5$
- $1 \le u, v \le N$
Community Discussion