I. Ý tưởng

Đối với bài toán này, thoạt nhìn thì có rất nhiều dữ kiện có thể sử dụng để giải.

Một trong những cách giải tốt ở đây, đó chính là đưa về một bài toán con để giải một bài toán chính.

Thế thì đặt ra câu hỏi ở đây là:

• Cho một cây \(n\) đỉnh và một tập \(k\) đỉnh \(\{v_1, v_2, \dots, v_k\}\) với \((k \leq n)\).
• Gọi kích thước của một cây khung là tổng số lượng cạnh của cây khung đó.
• Ta cần tìm kích thước cây khung nhỏ nhất bao trùm \(k\) đỉnh đã cho ?

II. Bài toán con

Bài trên là một trong những bài kinh điển về cây khung bao trùm nhỏ nhất.

a) Định nghĩa:

• Ta xét trên một cây tạo bởi \(k\) đỉnh \(\{v_1, v_2, \dots, v_k\}\).
• Gọi \(h(u)\) là độ sâu của đỉnh \(u\) so với gốc cây.
• Gọi \(d(u, v)\) là khoảng cách giữa \(2\) đỉnh trên cây (tất nhiên lấy theo số cạnh trên đường đi ngắn nhất).
• Gọi \(lca(u, v)\) là tổ tiên chung nhỏ nhất giữa \(2\) đỉnh trên cây (tất nhiên lấy theo đỉnh gần nhất có thể).
• Dễ chứng minh được \(d(u, v) = h(u) + h(v) - 2 \times h(lca(u,v))\).

Ta có thể đi từ đỉnh \(u\), lên gốc cây, rồi về lại đỉnh \(v\). Sau đó loại tất cả những đỉnh là cha của tổ tiên chung nhỏ nhất thì ta được đường đi ngắn nhất từ \(u\) đến \(v\).

b) Thuật toán:

• Thực hiện duyệt đồ thị theo chiều sâu, hay còn gọi là DFS.
• Không mất tính tổng quát ta sắp xếp lại các đỉnh đã thăm theo thứ tự duyệt: Bây giờ đỉnh \(v_i\) đã luôn được thăm trước đỉnh \(v_{i+1}\) với mọi \(1 \leq i < k\).
• Có thể thấy rằng cây khung bao phủ \(k\) đỉnh nhỏ nhất có kích thước là \(S = \underset{i=1}{\overset{k}{\Large \Sigma}} \frac{d(v_i, v_{i+1})}{2}\) với \(v_{n+1} = v_1\).

  Vì một đỉnh trong cây khung không cần thăm nhiều lần, và mọi cách sắp xếp lại một số đỉnh bất kì không theo thứ tự duyệt đều mang kết quả không tốt hơn, nên đây là cây khung bao trùm nhỏ nhất.

c) Độ phức tạp:

• Phụ thuộc chủ yếu vào đoạn tính tổ tiên chung nhỏ nhất \(lca(u, v)\), chỉ cần \(O(n \log n)\) là đủ tốt chứ không cần tới \(O(n)\).
• Các đoạn duyệt, sắp xếp và tính toán kết quả chỉ cần mất \(O(n)\) nếu bạn làm khéo.

III. Bài toán chính

Áp dụng bài toán con đã giải được ở trên vào phần bài chính, ta giải bài như sau

Lưu ý rằng phần độ phức tạp \(O(t_1 + t_2 + \dots + t_n)\) ta coi như hằng số.

a) Định nghĩa:

• Gọi \(f(x)\) là số lượng bài phân biệt tối đa có thể xuất hiện trong contest của người \(x\).
• Gọi \(S_j = \{v_{j_1}, v_{j_2}, \dots, v_{j_k}\}\) là tập các problem-setter có sở trường dạng bài \(j\).

b) Ý tưởng:

• Với mỗi giá trị \(x\), ta có \(f(x)\) chính là số lượng giá trị \(j\) khác nhau mà \(x\) nằm trong cây khung nhỏ nhất bao chứa \(S_j\).
• Hay nói cách khác là với mỗi tập \(S_j\), ta tăng tất cả \(f(x)\) lên \(1\) với mọi \(x\) thuộc cây khung nhỏ nhất chứa mọi đỉnh có trong \(S_j\).

c) Tiếp cận:

• Nếu bỏ qua bài toán con, ta có thể trâu qua từng tập \(S_j\) và duyệt các \(x\) để tăng giá trị \(f(x)\) một cách lần lượt trong thời gian \(O(n^3)\).
• Nhưng nhìn chung thì ta có một cách trâu đơn giản với \(O(n \log n)\) tiền xử lí bài toán con và \(O(n^2)\) việc duyệt qua từng giá trị \(x\) để tăng \(f(x)\).
• Nhưng nhận thấy rằng khi đi duyệt đỉnh theo thứ tự DFS, có những đỉnh sẽ lần lượt được thêm vào hoặc bỏ ra, từ đó cho ta 2 ý tưởng

Cách 1: Sử dụng cấu trúc dữ liệu để thêm bớt một đỉnh có trong cây khung nhỏ nhất bao trùm và tăng toàn bộ các giá trị \(f(x)\) trong \(O(\log n)\).

Cách 2: Ta sử dụng thuật toán cộng dồn trên cây đi từ trên xuống mà không cần động tới cấu trúc dữ liệu nào, mỗi lần tính mất không quá \(O(1)\).

d) Thuật toán \(O(n \log^2 n)\):

• Kết hợp kĩ thuật dsu on tree (sack) với cấu trúc dữ liệu C++std::set
• Mỗi lần duyệt DFS xong một đỉnh \(u\), và đi về lên lại cha của \(u\), thì ta sẽ hợp lại tất cả cây khung chứa các con của \(u\).
• Khi hợp các cây con của đỉnh \(u\), ta hợp tất cả các cây có kích thước nhỏ vô cây có kích thước lớn nhất.
• Có thể chứng minh được là nó không hợp cây quá \(O(\log n)\) lần, mỗi lần không quá \(O(n)\) đỉnh, và mỗi đỉnh không mất quá \(O(\log n)\) thời gian, tổng cộng lại là \(O(n \log^2 n)\).

e) Thuật toán \(O(n \log n)\)

• Duyệt các problem-setter theo chiều sâu và sắp xếp lại các đỉnh theo thứ tự xuất hiện.
• Với mỗi giá trị \(j = 1 \rightarrow m\), ta cập nhật \(\begin{cases} f(v_{j_i}) \text{ += } 1 & \forall i = 1 \rightarrow k \\ f(lca(v_{j_i}, v_{j_{i+1}})) \text{ -= } 1 & \forall i = 1 \rightarrow k - 1 \\ \end{cases}\)
• Cuối cùng ta duyệt DFS trên cây lại \(1\) lần nữa và cộng dồn trên cây để tính đáp án.
• Mỗi đỉnh ta chỉ cần sử dụng lca mất \(O(\log n)\) nên tổng lại là \(O(n \log n)\).

f) Thuật toán \(O(n)\)

• Bạn đọc có thể thử cải tiến LCA để dựng trong \(O(n)\) và truy vấn trong \(O(1)\).