PreVOI 2025 - Contest 3 - Thử thách trên cây
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 tạo một đồ thị dạng cây gồm ~n~ đỉnh, đỉnh thứ ~i~ ~(1 \le i \le n)~ có nhãn là số nguyên ~a_i~. Có ~q~ thử thách, thử thách thứ ~t~ ~(1 \le t \le q)~ được mô tả bằng hai số nguyên ~u, v~ ~(1 \le u, v \le n)~ cần thực hiện:
Tìm đường đi đơn từ đỉnh ~u~ đến đỉnh ~v~, giả sử đường đi đơn ~u = x_1, x_2, \dots, x_k = v~;
Chọn ra ~s~ (~s~ lẻ) nhiều nhất các chỉ số ~p_1, p_2, \dots, p_s~ sao cho:
~1 \le p_1 < p_2 < \dots < p_s \le k~ và ~a_{x_{p_1}} < a_{x_{p_2}} > a_{x_{p_3}} < \dots > a_{x_{p_s}}~.
Yêu cầu: Với mỗi thử thách hãy cho biết ~s~ lớn nhất có thể chọn được.
Input
Dòng đầu 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 không âm ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^9)~;
Dòng thứ ~i~ ~(1 \le i \le n-1)~ trong số ~n-1~ dòng tiếp theo chứa hai số nguyên ~x_i, y_i~ mô tả một cạnh của cây;
Dòng thứ ~t~ ~(1 \le t \le q)~ trong ~q~ dòng tiếp theo chứa hai số ~u, v~ mô tả thử thách.
Output
Gồm ~q~ dòng, mỗi dòng chứa một số nguyên ~s~ là đáp án của thử thách tương ứng.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n, q \le 100~ và ~a_i = i~ |
| 2 | ~15\%~ | ~1 \le a_i \le 2~ và cây có dạng đường thẳng |
| 3 | ~15\%~ | ~1 \le a_i \le 2~ |
| 4 | ~15\%~ | ~a_i = i~ |
| 5 | ~15\%~ | Cây có dạng đường thẳng |
| 6 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
7 2
1 2 1 2 1 2 1
1 2
1 3
2 4
2 5
3 6
6 7
5 7
7 3
Sample Output 1
5
3
Bình luận
Subtask Đường Thẳng Nè Mọi Người CLIMBING