Hành Trình Trên Cây Cổ Thụ

Buổi 62 — Sqrt Decomposition & Mo
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Một cây cổ thụ có N nút đánh số từ 1 đến N, nút thứ i có màu c_i. Có Q truy vấn, mỗi truy vấn cho hai nút u, v, hỏi có bao nhiêu màu khác nhau xuất hiện trên đường đi đơn từ u đến v.

Sử dụng Euler Tour kết hợp với thuật toán Mo trên cây (Mo's algorithm on tree).

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 100000). Dòng thứ hai chứa N số nguyên c_1, c_2, ..., c_N (1 ≤ c_i ≤ 100000). N-1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v mô tả một cạnh của cây. Q dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (1 ≤ u, v ≤ N).

Dữ liệu ra

Với mỗi truy vấn, in ra số lượng màu khác nhau trên đường đi từ u đến v trên một dòng.

Ví dụ
Input Output
5 3\n1 2 1 3 2\n1 2\n1 3\n2 4\n2 5\n4 5\n4 3\n1 4 2\n3\n3
Giới hạn
  • 1 ≤ N, Q ≤ 100000
  • 1 ≤ c_i ≤ 100000
  • 1 ≤ u, v ≤ N
Draft saved