Đây là một bài toán bảng thưa khá cơ bản, bạn có thể đọc thêm về cách cài đặt ở [đây.](https://wiki.vnoi.info/vi/algo/data-structures/rmq)
**Thuật toán:**
- Gọi $f(u, k)$ là đỉnh kết thúc khi bắt đầu từ đỉnh u và đi $2^k$ bước. Dễ thấy có thể tính trước giá trị này qua công thức $f(u, k) = f(f(u, k-1), k-1))$ với mọi $k > 0$, với $f(u, 0)$ là đỉnh mà u có cạnh ra nối tới.
- Khi đó, với mỗi truy vấn dạng $(u, x)$, ta sẽ chuyển từ đỉnh $u$ đến $f(u, k)$ với mọi bit $k$ bật trong biểu diễn nhị phân của $x$. Độ phức tạp của thuật toán là $O(32(n+q))$, do ta phải chuyển trạng thái tối đa $32$ lần (vì $log(10^9) = 32$).
***Lưu ý! Bài này chỉ áp dụng cho trường hợp mỗi đỉnh có tối đa 1 cạnh ra, do chỉ khi đó ta mới biết được chắc chắn mình sẽ đi hướng nào.***
**Code mẫu:**
```cpp
#include<bits/stdc++.h>
#define fu(i, a, b) for(int i = (a); i < (b); i++)
#define fub(i, a, b) for(int i = (a); i <= (b); i++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int lim = 1e18;
const int N = 1e5 + 5;
const int M = 1e9 + 7;
const int LG = 31;
int n, q;
int to[N];
int nxt[LG][N];
void sparse(int n){
fub(i, 1, n){
nxt[0][i] = to[i];
}
fu(i, 1, LG)fub(j, 1, n)nxt[i][j] = nxt[i-1][nxt[i-1][j]];
}
int des(int u, int x){
fu(i, 0, LG){
if((x >> i)&1)u = nxt[i][u];
}
return u;
}
signed main(){
fastio;
cin >> n >> q;
fub(i, 1, n)cin >> to[i];
sparse(n);
fub(i, 1, q){
int u, x; cin >> u >> x;
cout << des(u, x) << '\n';
}
}
nihahaha
Created at
10 likes