Subtask 1

Subtask đầu tiên chúng ta làm y như những gì mà đề yêu cầu. Đầu tiên ta có thể nhận xét là các đỉnh trong đồ thị có thể biểu diễn dưới dạng nhị phân: \(1\) là đã biết thông tin, \(0\) là chưa biết thông tin. Khi ta gọi truy vấn loại \(1\), có dạng 1 X K, ta sẽ cập nhất tất cả các bit trong cây con gốc \(X\) mà có độ sâu không quá \(K\) (tức là khoảng cách từ các đỉnh đó tới \(X\) trong cây con là không lớn hơn \(K\)) thành \(1\). Ta có thể sử dụng thuật toán DFS để giải quyết. Còn khi gặp truy vấn loại \(2\), có dạng 2 X K, ta một lần nữa sử dụng DFS để đểm tất cả các bit bật (là bit \(1\)) trong cây con gốc \(X\) độ sâu không quá \(K\). Độ phức tạp tất nhiên là \(O(Q \times N)\), với \(Q\) là số truy vấn và \(N\) là số đỉnh của cây.

Subtask 2

Có một nhận xét quan trọng ở subtask này đó là một đỉnh chỉ đảo bit từ \(0\) sang \(1\) đúng một lần duy nhất. Như vậy thì sau khi đã xét qua truy vấn cập nhật tại đỉnh \(X\) thì mọi truy vấn hỏi một trong các đỉnh thuộc cây con \(X\) sau đó kết quả đều chỉ có duy nhất mà thôi, còn các truy vấn cập nhật một trong các đỉnh thuộc cây con \(X\) về sau ta đều có thể bỏ qua (do không còn giá trị có thể thay đổi nữa). Một hướng giải quyết có liên quan tới các subtask về sau đó là sử dụng kỹ thuật làm phẳng cây. Ta có thể sử dụng thuật toán DFS để duyệt các đỉnh trong cây theo thứ tự, duyệt đến đâu thì thêm đỉnh đó vào một vector. Lúc này thì với mỗi đỉnh \(X\), tất cả các đỉnh thuộc cây con của nó sẽ có dạng một dãy các phần tử liên tiếp thuộc vector, và với truy vấn cập nhật thì việc của ta chỉ là đặt tất cả các phần tử đó thành giá trị \(1\), và với truy vấn đếm thì ta chỉ việc in ra số phần tử có giá trị \(0\) trong dãy. Dễ thấy đây chỉ là một bài toán segment tree cơ bản, ta thu được thuật toán với độ phức tạp \(O((N+Q)logN)\).

Subtask 3

Ở subtask này ta chỉ có mỗi truy vấn loại \(2\). Vẫn theo ý tưởng làm phẳng cây, nhưng lần này ta sẽ xây một cái merge-sort tree. Mỗi node của cây sẽ là một vector chứa độ sâu tính từ nút gốc của cây con của các đỉnh ban đầu có bit bật (vì ta đang đếm những nhân viên đã biết). Như vậy với mỗi node trong cây, tương ứng với một cây con, ứng một đoạn [L,R] trong mảng làm phẳng cây, là một vector chứa độ sâu của các đỉnh có bit bật có độ sâu được tính từ node gốc cây con đó. Sau khi đã có được một cái merge-sort tree thì với mỗi truy vấn đếm có dạng X K, ta chỉ đơn giản sử dụng chặt nhị phân để đếm số giá trị nhỏ hơn hoặc bằng \(K\) trong đoạn quản lý bởi cây con gốc \(X\) đó. Độ phức tạp thu được là \(O(NlogN + Qlog^2N)\) hoặc có thể tệ hơn là \(O((N+Q)log^2N)\) nếu như merge-sort tree được xây không tối ưu. Cả hai cách làm đều ăn trọn điểm của subtask này.

Subtask 4

Chúng ta có thể khiến cho cách giải của subtask \(3\) hoạt động ngay cả khi có thêm các truy vấn cập nhật bằng cách sử dụng treaps trong merge-sort tree. Theo đó, merge-sort tree sẽ lưu mọi đỉnh ở mỗi node, bao gồm cả các đỉnh bit bằng \(0\) (tắt). Hiển nhiên, khóa tìm kiếm \(X\) của các node trong treaps sẽ là độ sâu của các đỉnh. Một vấn đề ta cần giải quyết đó là khi ta cập nhật một node ở trong merge-sort tree, ta cũng cần phải cập nhật mọi node ở trên nó. Và điều này sẽ rất chậm trong các bộ test lớn. Vậy nên ta có một hướng giải quyết chính là ta sẽ xóa hết đỉnh bit \(0\) bị bật trong các treaps (tức là các treaps chỉ lưu các đỉnh bit \(0\) mà chưa bị bật). Tuy thao tác cập nhật các node phía trên vẫn khá lớn, nhưng ta chỉ phải xóa đi các bit \(0\) đúng một lần, và ta nhận xét tổng thao tác này không vượt qua \(Nlog^2N\). Độ phức tạp của cách giải trên sẽ là \(O((N+Q)log^2N)\), hay \(O(N*\sqrt Q)\) nếu sử dụng chia căn các truy vấn (cách này mình sẽ không đi sâu thêm).

Subtask 5

Độ phức tạp trong cách làm của subtask này không tốt hơn độ phức tạp trong subtask trước là nhiêu, nhưng thời gian chạy sẽ được cải thiện hơn đáng kể. Thay vì dựng một cái segment tree trên mảng làm phẳng cây và sau đó xây dựng các cấu trúc dữ liệu cho độ sâu của các node trong segment tree, ta sẽ làm ngược lại. Ta xây một cái segment tree trên các độ sâu và với mỗi node trong segment tree, ta lưu các đỉnh ứng với các độ sâu đó, và tạo thêm một cái segment tree nữa quản lý thời điểm xuất hiện của các đỉnh trong quá trình làm phẳng cây. Các segment tree này sẽ giúp cho việc đếm các đỉnh có bit bật xuất hiện trong một đoạn. Nếu cài khéo, thời gian và bộ nhớ trong quá trình dựng cây sẽ không chiếm nhiều – các lá ở mỗi segment tree sẽ ứng với các đỉnh khác nhau trong node mà segment tree đang được dựng. Do đó ta cũng có thể áp dụng merge-sort tree. Do ta không cần sử dụng treaps, thời gian thực hiện mỗi truy vấn đếm sẽ nhanh hơn rất nhiều (dù xét về lý thuyết thì độ phức tạp vẫn giữ nguyên). Với các truy vấn cập nhật thì ta sử dụng ý tưởng sẽ khác, đó là việc mỗi đỉnh bit \(0\) chỉ bật lên đúng một lần. Chúng ta sử dụng segment tree để lưu thông tin trong mỗi node cho biết nó có tồn tại một đỉnh có thể bật được hay không. Khi ta cập nhật, ta sẽ tìm tất cả các đỉnh như vậy thuộc khoảng trong truy vấn và cập nhật cây. Tổng các thao tác như vậy sẽ không vượt quá \(Nlog^2N\). Độ phức tạp cuối cùng ta thu được là \(O((N+Q)log^2N)\).