题目链接：传送门

Description

给定一棵树，每个节点有权值，每次查询节点 (u,v) 以及 x ，问 u 到 v 路径上的某个节点与 x 异或最大的值是多少。

Solution

首先可以将树上问题转化到序列上做。如果不是查询区间的话，我们可以直接使用01Trie来做，如果需要查询区间的话，自然就想到将它可持久化。我们在从根开始dfs时，建出可持久化01Trie，对于一个询问（u,v），我们只要求出(u, Lca)和(v, Lca)的答案再取max即可

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
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e5 + 10, Maxm = 20;

int N, M;
int e, Begin[Maxn], To[Maxn * 2], Next[Maxn * 2];
int Root[Maxn], Deep[Maxn];
int A[Maxn], anc[Maxn][21];

namespace DS
{
    int Son[Maxn * 20][2], Sum[Maxn * 20];
    int cnt;

    inline void insert (int &now, int pre, int w)
    {
        now = ++cnt;
        int now1 = now, now2 = pre;
        for (int i = 17; i >= 0; --i)
        {
            int x = w >> i & 1;
            Son[now1][x] = ++cnt;
            Son[now1][x ^ 1] = Son[now2][x ^ 1];
            if (!Son[now2][x])
                Sum[Son[now1][x]] = 1;
            else 
                Sum[Son[now1][x]] = Sum[Son[now2][x]] + 1;
            now1 = Son[now1][x], now2 = Son[now2][x];
        }
    }

    inline int query (int now, int pre, int w)
    {
        int now1 = now, now2 = pre;
        int ans = 0;
        for (int i = 17; i >= 0; --i)
        {
            int x = w >> i & 1;
            //cout<<x<<endl;
            //cout<<now1<<" "<<now2<<" "<<Son[now1][x ^ 1]<<" "<<Son[now1][x]<<" "<<Sum[Son[now1][x ^ 1]]<<" "<<Sum[Son[now1][x]]<<endl;
            if ((Sum[Son[now1][x ^ 1]] - Sum[Son[now2][x ^ 1]]) > 0)
            {
                ans += (1 << i);
                now1 = Son[now1][x ^ 1];
                now2 = Son[now2][x ^ 1];
            }
            else 
            {
                now1 = Son[now1][x];
                now2 = Son[now2][x];
            }
        }
        return ans;
    }
}

inline void Init ()
{
    e = 0;
    memset(Begin, 0, sizeof Begin);
    memset(DS :: Sum, 0, sizeof DS :: Sum);
    memset(DS :: Son, 0, sizeof DS :: Son);
    DS :: cnt = 0;
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

inline void dfs (int x, int fa)
{
    DS :: insert(Root[x], Root[fa], A[x]);
    anc[x][0] = fa;
    Deep[x] = Deep[fa] + 1;
    for (int i = 1; i <= 20; ++i) anc[x][i] = anc[anc[x][i - 1]][i - 1];
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa) continue;
        dfs(y, x);
    }
}

inline int Lca (int x, int y)
{
    if (Deep[x] < Deep[y]) swap(x, y);
    for (int i = 20; i >= 0; --i)
        if (Deep[anc[x][i]] >= Deep[y])
            x = anc[x][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; --i)
        if (anc[x][i] != anc[y][i])
            x = anc[x][i], y = anc[y][i];
    return anc[x][0];
}

inline int Query (int x, int y, int z)
{
    int LCA = Lca(x, y);
    return max(DS :: query (Root[x], Root[anc[LCA][0]], z), DS :: query (Root[y], Root[anc[LCA][0]], z));
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%d%d", &N, &M))
    {
        Init();
        for (int i = 1; i <= N; ++i)
            scanf("%d", &A[i]);
        for (int i = 1; i < N; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            add_edge (x, y);
            add_edge (y, x);
        }
        //Root[0] = ++DS :: cnt;
        //DS :: init(Root[0], 0);
        dfs(1, 0);
        while (M--)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            printf("%d\n", Query (x, y, z));
        }
    }
    return 0;
}