K-th nhỏ nhất trên đường đi của cây

Buổi 30 — Persistent Segment Tree
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho cây gốc $1$ gồm $n$ đỉnh, đỉnh $i$ có giá trị $a_i$. Mỗi truy vấn $(u,v,k)$: xét các đỉnh trên đường đi đơn từ $u$ đến $v$ (cả hai đầu), tìm giá trị nhỏ thứ $k$.

Dữ liệu vào

Dòng đầu: $n,q$. Dòng hai: $n$ số $p_1,\dots,p_n$ với $p_1=0$ và $p_i<i$ là cha của $i$. Dòng ba: $n$ số $a_i$. Sau đó $q$ dòng: $u,v,k$ ($1\le k\le$ số đỉnh trên đường đi).

Dữ liệu ra

Với mỗi truy vấn in đáp án.

Ví dụ

Input

5 5
0 1 2 3 2
2 4 -6 4 10
2 2 1
1 3 2
1 5 1
2 1 1
4 3 2

Output

4
2
2
2
4
Giới hạn
  • $1\le n,q\le 10^5$; $|a_i|\le 10^9$.
  • Thời gian: 2 giây; bộ nhớ: 256 MB.
Draft saved