Tóm tắt đề bài

Cho một rừng cây (đồ thị không chu trình) gồm \(n\) đỉnh và \(m\) cạnh. Có \(q\) truy vấn, mỗi truy vấn cho hai đỉnh \(x\) và \(y\).

• Nếu \(x\) và \(y\) thuộc cùng một thành phần liên thông (TPLT), kết quả là \(0\).
• Nếu \(x\) và \(y\) thuộc hai TPLT khác nhau (\(X\) và \(Y\)), ta xét tất cả \(|X| \times |Y|\) cách thêm một cạnh nối một đỉnh \(u \in X\) với một đỉnh \(v \in Y\). Khi đó \(X\) và \(Y\) sẽ hợp nhất thành một cây mới.
• Yêu cầu: Tính tổng đường kính của các cây mới tạo thành trong tất cả \(|X| \times |Y|\) trường hợp.

Phân tích

1. Đường kính của cây sau khi nối

Giả sử ta nối đỉnh \(u \in X\) và \(v \in Y\) bằng một cạnh. Gọi \(D(X)\) và \(D(Y)\) lần lượt là đường kính của hai cây ban đầu. Gọi \(f(u, X)\) là khoảng cách xa nhất từ đỉnh \(u\) đến một đỉnh bất kỳ trong cây \(X\).
Đường kính của cây mới, ký hiệu là \(D_{new}\), sẽ là giá trị lớn nhất trong ba khả năng:

1. Đường kính cũ của cây \(X\): \(D(X)\)
2. Đường kính cũ của cây \(Y\): \(D(Y)\)
3. Đường đi dài nhất đi qua cạnh mới \((u, v)\): \(f(u, X) + 1 + f(v, Y)\)

Vậy:

2. Tính \(f(u, X)\)

Với mỗi đỉnh \(u\) trong một cây, \(f(u, X)\) chính là khoảng cách từ \(u\) đến đỉnh xa nhất trong cây đó. Giá trị này có thể được tính bằng cách:

• Tìm hai đầu mút của đường kính cây \(X\), gọi là \(A\) và \(B\).
• \(f(u, X) = \max(dist(u, A), dist(u, B))\).
  Điều này có thể thực hiện bằng 3 lần BFS/DFS cho mỗi TPLT.

3. Tính tổng đường kính

Với mỗi cặp TPLT \((X, Y)\), ta cần tính:

Trong đó \(D_{max} = \max(D(X), D(Y))\).

Để tính nhanh tổng này, ta có thể:

• Sắp xếp các giá trị \(f(v, Y)\) của các đỉnh trong cây \(Y\) theo thứ tự tăng dần.
• Với mỗi \(u \in X\), ta cần tìm các \(v \in Y\) sao cho \(f(u, X) + f(v, Y) + 1 > D_{max}\), tức là \(f(v, Y) > D_{max} - f(u, X) - 1\).
• Sử dụng tìm kiếm nhị phân (lower_bound) để tìm vị trí phân tách, sau đó dùng mảng cộng dồn (prefix sum) để tính tổng các giá trị \(f(v, Y)\) lớn hơn ngưỡng đó.

Hướng giải quyết

1. Tiền xử lý:
   • Tìm các TPLT. Với mỗi TPLT, tìm đường kính và tính mảng \(f(u, X)\) cho mọi đỉnh \(u\).
   • Lưu danh sách các giá trị \(f(u, X)\) của từng TPLT, sắp xếp chúng và xây dựng mảng cộng dồn.
2. Xử lý truy vấn:
   • Nếu \(x, y\) cùng TPLT: in 0.
   • Để tối ưu, luôn duyệt qua TPLT có ít đỉnh hơn (tương tự kỹ thuật Small-to-Large).
   • Sử dụng std::unordered_map hoặc std::map để lưu lại kết quả các cặp TPLT đã tính (memoization) vì có thể có nhiều truy vấn trùng cặp TPLT.
   • Với mỗi \(u\) trong TPLT nhỏ hơn, dùng lower_bound trên danh sách \(f\) của TPLT lớn hơn để tính tổng theo công thức đã phân tích.

Độ phức tạp

• Tiền xử lý: \(O(n + m)\) để tìm TPLT và tính \(f(u, X)\). Sắp xếp mất \(O(n \log n)\).
• Truy vấn: Trong trường hợp xấu nhất, độ phức tạp có thể lên tới \(O(Q \sqrt{N} \log N)\) hoặc tốt hơn nhờ memoization. Việc luôn duyệt qua TPLT nhỏ hơn giúp giảm đáng kể số phép tính.
• Bộ nhớ: \(O(n + m)\) để lưu đồ thị và các thông tin TPLT.