「CF1479D」Odd Mineral Resource

$Link$

有一棵 $n$ 个点的树，每个点上都有一个颜色。

有 $q$ 次询问，每次询问路径 $u\to v$ 上颜色编号在 $[l,r]$ 内的出现奇数次的颜色。如果存在，输出随意一个满足条件的颜色，否则输出 $-1$。

$1\le n,q\le3\times10^5$，时间限制 $5s$。

首先没有修改操作的树上区间询问，可以想到主席树。

出现奇数次算，偶数次不算，可以想到异或操作。

在主席树上直接把编号异或起来？很容易就可以构造出一组数据 $hack$ 掉。

但是这个思路感觉是能做的，只不过因为编号之间异或起来会互相影响会导致 $WA$。

我们直接暴力哈希，把每个编号重新赋一个在 $[1,2^{64})$ 内的权值，这样，冲突的概率就很小了。

时间复杂度 $O(n\log n)$。

$code$

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <time.h>
#define ll long long
#define mid ((l + r) >> 1)
using namespace std;
inline int read()
{
    int f = 1, x = 0;
    char ch;

    do{
        ch = getchar();
        if (ch == '-')
            f = -1;
    }while(ch < '0' || ch > '9');
    do{
        x = x * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return f * x;
}
const int N = 3e5;

int n, m;
int root[N + 1], color[N + 1];
ll val[N + 1];
namespace seg
{
ll tr[N * 32 + 1];
int lson[N * 32 + 1], rson[N * 32 + 1], tot;
inline void copy(int from, int to)
{
    tr[to] = tr[from];
    lson[to] = lson[from];
    rson[to] = rson[from];
    return;
}
inline int update(int now, int l, int r, int c)
{
    tot++;
    copy(now, tot);
    now = tot;
    if (l == r) {
        tr[now] ^= val[c];
        return now;
    }
    if (c <= mid)
        lson[now] = update(lson[now], l, mid, c);
    else
        rson[now] = update(rson[now], mid + 1, r, c);
    tr[now] = tr[lson[now]] ^ tr[rson[now]];
    return now;
}
inline int query(int a, int b, int c, int d, int l, int r, int L, int R)
{
    if (l == r)
        return tr[a] ^ tr[b] ^ tr[c] ^ tr[d]?l:-1;
    if (l >= L && r <= R) {
        if (tr[lson[a]] ^ tr[lson[b]] ^ tr[lson[c]] ^ tr[lson[d]])
            return query(lson[a], lson[b], lson[c], lson[d], l, mid, L, R);
        if (tr[rson[a]] ^ tr[rson[b]] ^ tr[rson[c]] ^ tr[rson[d]])
            return query(rson[a], rson[b], rson[c], rson[d], mid + 1, r, L, R);
        return -1;
    }
    int ans = -1;

    if (L <= mid)
        ans = max(ans, query(lson[a], lson[b], lson[c], lson[d], l, mid, L, R));
    if (ans != -1)
        return ans;
    if (R > mid)
        ans = max(ans, query(rson[a], rson[b], rson[c], rson[d], mid + 1, r, L, R));
    return ans;
}
}
struct Edge {
    int to, next;
} edge[N * 2 + 1];
int start[N + 1], tot;
int fa[N + 1][19], dep[N + 1];

inline void addedge(int u, int v)
{
    edge[++tot] = { v, start[u] };
    start[u] = tot;
    edge[++tot] = { u, start[v] };
    start[v] = tot;
    return;
}
inline void dfs(int u)
{
    root[u] = seg::update(root[fa[u][0]], 1, n, color[u]);
    dep[u] = dep[fa[u][0]] + 1;
    for (int i = start[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v != fa[u][0]) {
            fa[v][0] = u;
            dfs(v);
        }
    }
}
inline int lca(int u, int v)
{
    if (dep[u] > dep[v])
        swap(u, v);
    for (int i = 18; i >= 0; i--)
        if (dep[fa[v][i]] >= dep[u])
            v = fa[v][i];
    if (u == v)
        return u;
    for (int i = 18; i >= 0; i--) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
inline ll rrand()
{
    return 1ll * rand() << 45 | 1ll * rand() << 30 | 1ll * rand() << 15 | 1ll * rand();
}
int main()
{
    srand(time(0));
    memset(val, -1, 8 * (N + 1));
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        color[i] = read();
        if (val[color[i]] == -1)
            val[color[i]] = rrand();
    }
    for (int i = 1; i < n; i++)
        addedge(read(), read());

    dfs(1);
    for (int i = 1; i <= 18; i++)
        for (int j = 1; j <= n; j++)
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read(), l = read(), r = read(), llca = lca(u, v);
        printf("%d\n", seg::query(root[u], root[v], root[llca], root[fa[llca][0]], 1, n, l, r));
    }

    return 0;
}