IPST60: Deep

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
const int M = 300 + 5;
const int logN = log2(2e5);

vector<int> branch, adj[M];
int chd[N][logN + 1];
bool hasBranch[N];

int s, a, b;
int rndDir(){
    int res = (s & 8) >> 3;
    s = (s * a + b) % 40507;
    return res;
}

void dive(int &u, int &rnk){
    if(hasBranch[u]){
        return;
    }
    int depth = 0;
    int v = u;
    for(int e = logN; e >= 0; --e){
        if(!hasBranch[chd[v][e]]){
            v = chd[v][e];
            depth += 1 << e;
        }
    }
    depth += 1;
    if(depth <= rnk){
        rnk -= depth;
        u = chd[v][0];
        return;
    }
    for(int e = logN; e >= 0; --e){
        if((1 << e) <= rnk){
            u = chd[u][e];
            rnk -= 1 << e;
        }
    }
}

int main(){

    int nVertex, Q;
    scanf("%d%d", &nVertex, &Q);
    int nBranch = 0;
    for(int u = 1; u <= nVertex; ++u){
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        if(v1 == -1 && v2 == -1){
            hasBranch[u] = false;
            chd[u][0] = u;
        } else if(v1 == -1){
            hasBranch[u] = false;
            chd[u][0] = ++v2;
        } else if(v2 == -1){
            hasBranch[u] = false;
            chd[u][0] = ++v1;
        } else {
            hasBranch[u] = true;
            chd[u][0] = u;
            branch.push_back(u);
            adj[nBranch].push_back(++v1);
            adj[nBranch].push_back(++v2);
            ++nBranch;
        }
    }
    for(int e = 1; e <= logN; ++e){
        for(int u = 1; u <= nVertex; ++u){
            chd[u][e] = chd[chd[u][e - 1]][e - 1];
        }
    }
    while(Q--){
        int rnk;
        scanf("%d%d%d%d", &rnk, &s, &a, &b);
        int u = 1;
        while(rnk > 0){
            dive(u, rnk);
            if(rnk > 0 && hasBranch[u]){
                int i = lower_bound(branch.begin(), branch.end(), u) - branch.begin();
                u = adj[i][rndDir()];
                --rnk;
            }
        }
        cout << u - 1 << '\n';
    }

    return 0;
}