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

Xem dạng PDF
Gửi bài giải
Điểm: 150,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~ 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 là ~x_1, x_2, \dots, x_k = v~;
  • Chọn ra ~s~ (~s~ lẻ) nhiều nhất các chỉ số ~1 \le p_1 < p_2 < \dots < p_s \le k~ sao cho: ~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~ 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

  • Ghi ra ~q~ dòng, mỗi dòng chứa một số nguyên là đáp án của thử thách tương ứng.

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.