PreVOI 2025 - Đèn trang trí
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Alice mới mua một đèn chùm để trang trí trong Lễ giáng sinh năm nay. Đèn chùm gồm ~n~ đèn được biểu diễn bằng một cây gồm ~n~ nút, trong đó các nút tương ứng với các đèn, các cạnh là khung sắt cùng dây nối giữa các đèn. Đèn ~i~ ~(1 \le i \le n)~ ở trạng thái ban đầu là màu ~c_i~ ~(1 \le c_i \le 10^6)~ và có thể điều chỉnh được, cụ thể, nếu một đèn đang ở trạng thái sáng màu ~c~ thì có thể điều chỉnh để đèn sáng màu ~c-1~ nếu ~c > 1~ hoặc ~c+1~ nếu ~c < 10^6~.
Alice đã tập hợp lại ~q~ mong muốn của mọi người theo thứ tự ưu tiên giảm dần. Mong muốn thứ ~t~ ~(1 \le t \le q)~ là đoạn nối từ đèn ~u_t~ đến đèn ~v_t~ ~(1 \le u_t, v_t \le n; u_t \ne v_t)~ sẽ đối xứng, có nghĩa là khi liệt kê màu các đèn trên đường đi đơn từ đèn ~u_t~ đến đèn ~v_t~ cũng giống như liệt kê màu các đèn khi đi từ đèn ~v_t~ đến đèn ~u_t~.
Yêu cầu: Với mỗi giá trị ~t~ ~(1 \le t \le q)~, hãy giúp Alice tính số lần điều chỉnh ít nhất cần thực hiện từ trạng thái ban đầu để thỏa mãn ~t~ mong muốn đầu tiên.
Input
Dòng đầu tiên chứa hai số nguyên dương ~n, q~ ~(n, q \le 10^5)~;
Dòng thứ hai chứa ~n~ số nguyên dương ~c_1, c_2, \dots, c_n~ ~(c_i \le 10^6)~;
Dòng thứ ~k~ ~(1 \le k < n)~ trong ~n-1~ dòng sau chứa hai số nguyên dương ~i_k, j_k~ cho biết có dây nối trực tiếp giữa hai đèn ~i_k, j_k~ ~(1 \le i_k, j_k \le n; i_k \ne j_k)~ là cạnh của cây.
Dòng thứ ~t~ ~(1 \le t \le q)~ chứa hai số nguyên dương ~i_k, j_k~ cho biết mong muốn thứ ~t~.
Output
- Gồm ~q~ dòng, dòng thứ ~t~ ~(1 \le t \le q)~ cho biết số lần điều chỉnh ít nhất cần thực hiện từ trạng thái ban đầu để thỏa mãn ~t~ mong muốn đầu tiên.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n, q \le 10~; ~1 \le c_i \le 2~ và cây có dạng chuỗi thẳng |
| 2 | ~15\%~ | ~n, q \le 200~; ~1 \le c_i \le 2~ và cây có dạng chuỗi thẳng |
| 3 | ~10\%~ | ~n, q \le 200~ và cây có dạng chuỗi thẳng |
| 4 | ~20\%~ | ~n, q \le 200~ |
| 5 | ~20\%~ | ~n \le 10^5~ và cây có dạng chuỗi thẳng |
| 6 | ~15\%~ | Không có giới hạn gì thêm |
Sample Input 1
5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
1 3
3 5
1 5
Sample Output 1
2
4
6
Sample Input 2
5 3
1 2 3 4 5
1 2
1 3
3 4
3 5
2 3
4 5
3 4
Sample Output 2
1
2
4
Bình luận