Find smallest number exists odd times on path from u -> v(Hashing, probabilities)

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 3e5, cbit = 18;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
vector<int> adj[N + 1];
int depth[N + 1], f[N + 1][cbit + 1], tin[N + 1], tout[N + 1], timer, n, q;
int s[N + 1], a[N + 1];
struct FenwickTree
{
    int Tree[N + 1];
    void reset()
    {
        memset(Tree, 0, sizeof(Tree));
    }
    void add(int pos, int val)
    {
        for (; pos <= n; pos |= pos + 1)
        {
            Tree[pos] ^= val;
        }
    }
    int get(int pos)
    {
        int ret = 0;
        for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
        {
            ret ^= Tree[pos];
        }
        return ret;
    }
} tree;
vector<int> timeline[N + 1];
void read()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i)
    {
        s[i] = rd();
        s[i] = abs(s[i]);
    }
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        timeline[a[i]].push_back(i);
    }
    for (int i = 1; i < n; ++ i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}
void DFS(int u, int p)
{
    tin[u] = ++timer;
    for (int v : adj[u])
    {
        if (v == p)
        {
            continue;
        }
        depth[v] = depth[u] + 1;
        f[v][0] = u;
        for (int i = 1; i <= cbit; ++ i)
        {
            f[v][i] = f[f[v][i - 1]][i - 1];
        }
        DFS(v, u);
    }
    tout[u] = timer;
}
int LCA(int u, int v)
{
    if (depth[u] > depth[v])
    {
        swap(u, v);
    }
    int k = depth[v] - depth[u];
    for (int i = cbit; i >= 0; -- i)
    {
        if ((k >> i) & 1)
        {
            v = f[v][i];
        }
    }
    if (u == v)
    {
        return u;
    }
    for (int i = cbit; i >= 0; -- i)
    {
        if (f[v][i] != f[u][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    }
    return f[u][0];
}
int u[N + 1], v[N + 1], p[N + 1], l[N + 1], r[N + 1], low[N + 1], high[N + 1], res[N + 1];
int store[N + 1];
vector<pair<int, int> > query[N + 1];
void solve()
{
    DFS(1, 0);
    for (int i = 1; i <= q; ++ i)
    {
        cin >> u[i] >> v[i] >> l[i] >> r[i];
        p[i] = LCA(u[i], v[i]);
        low[i] = l[i];
        high[i] = r[i];
        res[i] = -1;
    }
    while(true)
    {
        bool stop = true;
        for (int i = 0; i <= n; ++ i)
        {
            query[i].clear();
        }
        for (int i = 1; i <= q; ++ i)
        {
            if (low[i] <= high[i])
            {
                stop = false;
                int mid = (low[i] + high[i])/2;
                query[l[i] - 1].emplace_back(0, i);
                query[mid].emplace_back(1, i);
            }
        }
        if (stop)
        {
            break;
        }
        tree.reset();
        for (int x = 0; x <= n; ++ x)
        {
            for (int u : timeline[x])
            {
                tree.add(tin[u], s[a[u]]);
                tree.add(tout[u] + 1, s[a[u]]);
            }
            for (auto &[t, i] : query[x])
            {
                int k = p[i];
                int cur = tree.get(tin[u[i]]) ^ tree.get(tin[v[i]]) ^ (a[k] <= x ? s[a[k]] : 0);
                if (t == 0)
                {
                    store[i] = cur;
                }
                else
                {
                    cur ^= store[i];
                    if (cur > 0)
                    {
                        high[i] = x - 1;
                        res[i] = x;
                    }
                    else
                    {
                        low[i] = x + 1;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= q; ++ i)
    {
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case #" << __ << ":" << '\n';
        read();
        solve();
    }
}