PreVOI 2025 - Contest 3 - Thử thách trên cây

Xem dạng PDF

Gửi bài giải

Điểm: 60,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong 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

Hãy đọc nội quy trước khi bình luận.