Editorial for Chạy bộ

Cho một cây bao gồm $n$ ~n~ đỉnh và $n - 1$ ~n - 1~ cạnh. Đếm số lượng đường đi dài nhất trên cây đã cho.

Chọn một đỉnh bất kỳ để làm gốc của cây.
Xét đỉnh $u$ ~u~ và cây con gốc $u$ ~u~:
- Xét một đỉnh $v$ ~v~ bất kỳ nằm trong cây con gốc $u$ ~u~, tập các đường đi $P_u$ ~P_u~ bắt đầu từ đỉnh $u$ ~u~ sẽ bao gồm đường đi $u - v$ ~u - v~.
- Xét hai đỉnh $v1$ ~v1~, $v2$ ~v2~ bất kỳ nằm ở hai nhánh khác nhau của cây con gốc $u$ ~u~, tập các đường đi $P_u$ ~P_u~ đi qua $u$ ~u~ sẽ bao gồm đường đi $v1 - u - v2$ ~v1 - u - v2~.
Tập tất cả các đường đi trong cây ban đầu là hợp của tất cả tập các đường đi $P_i$ ~P_i~ chứa đỉnh $i$ ~i~ trong cây con gốc $i$ ~i~.
Và $P_i \cap P_j = \varnothing$ ~P_i \cap P_j = \varnothing~ với $i \neq j$ ~i \neq j~, tức hai tập đường đi bất kỳ không chứa hai đường đi giống nhau.

Như trong hình trên, giả sử ta chọn đỉnh $1$ ~1~ là đỉnh gốc của cây.
- Tập các đường đi $P_1$ ~P_1~ chứa đỉnh $1$ ~1~ trong cây con gốc $1$ ~1~ là:
  - $1$ ~1~.
  - $1 - 2$ ~1 - 2~.
  - $1 - 2 - 3$ ~1 - 2 - 3~.
  - $1 - 2 - 3 - 5$ ~1 - 2 - 3 - 5~.
  - $1 - 2 - 3 - 4$ ~1 - 2 - 3 - 4~.
- Tập các đường đi $P_2$ ~P_2~ chứa đỉnh $2$ ~2~ trong cây con gốc $2$ ~2~ là:
  - $2$ ~2~.
  - $2 - 3$ ~2 - 3~.
  - $2 - 3 - 5$ ~2 - 3 - 5~.
  - $2 - 3 - 4$ ~2 - 3 - 4~.
- Tập các đường đi $P_3$ ~P_3~ chứa đỉnh $3$ ~3~ trong cây con gốc $3$ ~3~ là:
  - $3$ ~3~.
  - $3 - 5$ ~3 - 5~.
  - $3 - 4$ ~3 - 4~.
  - $4 - 3 - 5$ ~4 - 3 - 5~.
- Tập các đường đi $P_4$ ~P_4~ chứa đỉnh $4$ ~4~ trong cây con gốc $4$ ~4~ là:
  - $4$ ~4~.
- Tập các đường đi $P_5$ ~P_5~ chứa đỉnh $5$ ~5~ trong cây con gốc $5$ ~5~ là:
  - $5$ ~5~.
Tập tất cả đường đi trên cây ban đầu là hợp của tất cả tập các đường trên, tức là $P_1 \cup P_2 \cup P_3 \cup P_4 \cup P_5$ .
Và $P_i \cap P_j = \varnothing$ ~P_i \cap P_j = \varnothing~ với $1 \le i \neq j \le 5$ ~1 \le i \neq j \le 5~.

Từ nhận xét trên, ta chỉ cần đếm số lượng đường đi dài nhất trong các tập $P_i$ ~P_i~.
Để thực hiện bài toán trên, ta sử dụng kỹ thuật quy hoạch động trên cây như sau:
- Gọi $maxDepth_u$ ~maxDepth_u~ là độ sâu tối đa của cây con gốc $u$ ~u~ và $cntMaxDepth_u$ ~cntMaxDepth_u~ là số lượng đường đi bắt đầu từ đỉnh $u$ ~u~ trong $P_u$ ~P_u~ có độ dài bằng $maxDepth_u$ ~maxDepth_u~.
- Ta có thể tính các giá trị $maxDepth_u$ ~maxDepth_u~ và $cntMaxDepth_u$ ~cntMaxDepth_u~ bằng DFS trong độ phức tạp $O(n)$ ~O(n)~.
- Với mỗi đỉnh $u$ ~u~:
  - Nếu $u$ ~u~ chỉ có một nhánh thì độ dài và số lượng đường đi dài nhất trong $P_u$ ~P_u~ là $maxDepth_u$ ~maxDepth_u~ và $cntMaxDepth_u$ ~cntMaxDepth_u~.
  - Nếu $u$ ~u~ có hai nhánh trở lên thì độ dài đường đi dài nhất trong $P_u$ ~P_u~ là $max(maxDepth_{v1} + maxDepth_{v2} + 2)$ với $v_1$ ~v_1~, $v_2$ ~v_2~ là hai đỉnh con trực tiếp bất kỳ của $u$ ~u~. Với trường hợp này, ta có thể tính toán độ dài và số lượng đường đi dài nhất trong độ phức tạp $O(k*log(k))$ ~O(k*log(k))~ hoặc $O(k)$ ~O(k)~ với $k$ ~k~ là số lượng đỉnh con trực tiếp của $u$ ~u~.
Độ phức tạp: $O(n)$ ~O(n)~ hoặc $O(n*log(n))$ ~O(n*log(n))~.