Trạm dừng thứ K trên đường đi cây

Buổi 42 — LCA & Binary Lifting
Points
55
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Có $Q$ truy vấn, mỗi truy vấn gồm ba số $u, v, k$, yêu cầu tìm đỉnh thứ $k$ (đánh số từ $1$, với đỉnh thứ $1$ là $u$) nằm trên đường đi đơn từ $u$ đến $v$. Dữ liệu đảm bảo $1 \le k \le \text{số đỉnh trên đường đi từ } u \text{ đến } v$.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $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 ba số nguyên $u, v, k$.
Dữ liệu ra
  • In ra $Q$ dòng là chỉ số đỉnh tìm được cho từng truy vấn.
Ví dụ
Dữ liệu vào Dữ liệu ra
6 3
1 2
1 3
2 4
2 5
3 6
4 6 3
4 6 1
5 4 2
1
4
2
Giới hạn
  • $1 \le N, Q \le 10^5$
Draft saved