Hành Trình Trên Cây Cổ Thụ
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Đề 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
Community Discussion