Tổ tiên thứ K
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh gốc tại $1$. Với mỗi truy vấn gồm đỉnh $u$ và số nguyên $K$, hãy tìm tổ tiên thứ $K$ của $u$ (tổ tiên thứ $0$ là chính $u$, tổ tiên thứ $1$ là cha của $u$, ...). Nếu không tồn tại, in ra -1.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, Q$. $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 tiếp theo, mỗi dòng chứa hai số nguyên $u, K$.
Dữ liệu ra
Gồm $Q$ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.
Ví dụ
| Input | Output |
|---|---|
| 5 4 1 2 1 3 2 4 2 5 4 1 4 2 4 3 5 0 |
2 1 -1 5 |
Giới hạn
$1 \le N, Q \le 10^5$, $0 \le K \le N$.
Community Discussion