Subtask 1: \(1 \leq n, q \leq 2000\).

Duyệt hết tất cả các đỉnh trong tập để kiểm tra.
Độ phức tạp: \(O(N \times Q)\).

Subtask 2: \(1 \leq n, q \leq 50000\) và mỗi đỉnh có tối đa \(2\) cạnh nối trực tiếp.

Cây trong trường hợp này có thể coi như \(1\) đường thẳng, các tập cần xét sẽ là \(1\) hoặc \(2\) (trường hợp ngoài cây con) đoạn liên tiếp.

Ta có thể sử lý mỗi truy vấn theo thuật sau:

• Chọn ngẫu nhiên \(30\) phần tử trong tập.
• Với mỗi phần tử, kiểm tra xem màu của phần tử đó có thỏa mãn không, nếu có, thì đó là kết quả của truy vấn.
• Nếu xét hết \(30\) phần tử mà vẫn không tìm được màu thỏa mãn, ta chấp nhận in ra \(-1\) với xác xuất sai rất nhỏ \(\left(\dfrac{1}{2}\right)^{30}\).
• Để kiểm tra \(1\) màu có thỏa mãn không, ta có thể lưu mỗi màu \(1\) danh sách các vị trí xuất hiện và chặt nhị phân để đếm số lần xuất hiện trong đoạn.
  Độ phức tạp: \(O(N + Q \times 30 \times \log_{2}(N))\).

Subtask 3: \(1 \leq n, q \leq 50000, 1 \leq a_{i} \leq 2\).

Ta lưu \(2\) mảng \(f[i][j]\) là số lần xuất hiện màu \(j\) trong cây con gốc \(i\) và \(g[i][j]\) là số lần xuất hiện màu \(j\) trên đường đi từ \(1\) đến \(i\).

Với mỗi truy vấn, ta kiểm tra cả \(2\) màu, số lần xuất hiện của màu \(i\):

• Truy vấn loại 1: \(f[u][i]\).
• Truy vấn loại 2: \(f[1][i] - f[u][i]\).
• Truy vấn loại 3: \(f[u][i] + f[v][i] - 2 \times f[lca(u,v)][i] + a[lca(u,v)]\)

Độ phức tạp: \(O((N + Q) \times \log_{2}(N))\).

Subtask 4: \(1 \leq n, q \leq 50000\) và không có truy vấn loại \(3\).

Ta dùng thuật toán dfs để duỗi cây ra, bây giờ các đỉnh thuộc cây con gốc \(u\) nằm liên tiếp nhau trong dãy khi duỗi.

Đến đây, do không có truy vấn loại \(3\) nên ta có thể xử lý như trong subtask 2.
Độ phức tạp: \(O(N + Q \times 30 \times \log_{2}(N))\).

Subtask 5: không có ràng buộc nào thêm.

Đặt \(T = \sqrt{N}\).

Với mỗi truy vấn ta chia làm \(2\) trường hợp:

• Nếu lực lượng của tập \(\leq 2 \times T\) ta duyệt trâu để kiểm tra.
• Nếu lực lượng của tập \(> 2 \times T\) thì nếu tập đẹp thì tồn tại 1 màu xuất hiện nhiều hơn \(T\) lần. Đến đây ta có thể xử lý như \(subtask 3\), nhưng thay vì xét \(2\) màu, ta xét hết các màu có số lần xuất hiện trên cây lớn hơn \(T\) lần, có tối đa \(\dfrac{N}{T}\) màu như vậy.

Độ phức tạp \(O(N \times \log_{2}(N) + Q \times \sqrt{N})\).