Subtask 1

Ta sẽ lưu cha của từng đỉnh và nhảy đỉnh có độ sâu lớn hơn trong ~x~ và ~y~ cho đến khi chúng gặp nhau tại một điểm. Điểm này chính là điểm mà chúng ta cần tìm.

Độ phức tạp: ~O(q \cdot n)~

Subtask 2

Ta cài đặt như một bài toán ~LCA~ bình thường.

Độ phức tạp: ~O(q \cdot n \log n)~

Subtask 3

Ta sử dụng ~RMQ~ để trả lời truy vấn cho bài toán ~LCA~ trong ~O(1)~. VNOI đã từng có một bài viết về chủ đề này tại đây.

Độ phức tạp : ~O(n \log n + q)~

#include <bits/stdc++.h>
#define pii pair<int, int>
#define task "hihi"

using namespace std;
const int N = 2e5 + 5, LOG = 20, MOD = 1e9 + 7;  

int n, q; vector<int> adj[N];

int timedfs = 0, tin[N], tout[N], h[N], lg2[N];
pii st[LOG][N];
inline int get(int x, int y){
    if(tin[x] > tin[y]) swap(x, y);
    x = tin[x], y = tout[y];
    int i = lg2[y - x + 1];
    return min(st[i][x], st[i][y - (1 << i) + 1]).second;
}
void dfs(int i, int pre){
    tin[i] = tout[i] = ++timedfs;
    st[0][timedfs] = {h[i], i};
    for(int x : adj[i]){
        if(x == pre) continue;
        h[x] = h[i] + 1;
        dfs(x, i);
        tout[i] = ++timedfs;
        st[0][timedfs] = {h[i], i};
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    cin >> n >> q;

    for(int i = 2, x, y; i <= n; i++){
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    } 
    dfs(1, 1);
    for(int i = 1; i < LOG; i++){
        for(int j = 1; j + (1 << i) - 1 <= timedfs; j++){
            st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        }
    }   

    for(int i = 2; i <= timedfs; i++) lg2[i] = lg2[i / 2] + 1;

    int u, v, u_jump, v_jump, u_add, v_add;

    cin >> u >> v >> u_jump >> v_jump >> u_add >> v_add;

    int ans = 0;
    for(int i = 1; i <= q; i++){
        // cin >> u >> v;

        ans = ans ^ get(u, v);

        u = (1LL * u * u_jump + u_add) % n + 1;
        v = (1LL * v * v_jump + v_add) % n + 1;
    }

    cout << ans << "\n";
    return 0;
}