Cây Gia Phả Tăng Dần
Points
62
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề 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$
Community Discussion