Tổng Hai Đường Kính Khi Cắt Cạnh

Buổi 34 — Tree DP & Rerooting Dynamic Programming
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved