Cây Gia Phả Tăng Dần

Buổi 39 — DP + Data Structures Dynamic Programming
Points
62
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Cho một cây có $N$ đỉnh đánh số từ $1$ đến $N$, gốc tại đỉnh $1$. Mỗi đỉnh $u$ được gán một giá trị $A_u$.

Với mỗi đỉnh $u$, xét đường đi đơn từ gốc $1$ đến $u$, định nghĩa $dp[u]$ là độ dài dãy con tăng nghiêm ngặt dài nhất kết thúc tại $u$ trên đường đi đó.

Bạn cần trả lời $Q$ truy vấn, mỗi truy vấn gồm cặp $(u, X)$: hãy tìm giá trị lớn nhất của $dp[v]$ với $v$ là tổ tiên của $u$ (tính cả $u$) sao cho $A_v \le X$. Nếu không có đỉnh $v$ nào thỏa mãn, in ra 0.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $N$ và $Q$. Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$. $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh của cây. $Q$ dòng cuối cùng, mỗi dòng chứa hai số nguyên $u, X$.

Dữ liệu ra

Với mỗi truy vấn, in ra kết quả trên một dòng.

Ví dụ
Input Output
5 4
3 1 4 2 5
1 2
1 3
2 4
3 5
4 3
5 4
5 5
2 1
2
2
3
1
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $1 \le A_i, X \le 10^9$
Draft saved