「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$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#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;
}