## 【HDU-6191】Query on A Tree【Trie + DFS】

【HDU-6191】Query on A Tree【Trie + DFS】

Solution:

【注：[]内表示该结点的标号，:后面则是该结点的值】

```#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int SIZE = 29;
const int LIM = 1e5 + 10;
const int NIL = -1;
int role[LIM * (SIZE + 3)], trie[LIM * (SIZE + 3)][2], root[LIM], values[LIM], sz[LIM];
int trie_size, node_size;
int idx[LIM];

inline void init(int n) {
trie_size = node_size = 0;
memset(trie, 0, sizeof trie);
memset(role, 0, sizeof role);
memset(sz, 0, sizeof sz);
for (int i = 1; i <= n; i++)
}

void update(int &crt, int pre, int vpos, int d) {
crt = ++trie_size;
trie[crt][0] = trie[pre][0];
trie[crt][1] = trie[pre][1];
role[crt] = role[pre] + 1;
if (d == NIL) return;
int key = (values[vpos] >> d) & 1;
if (key) update(trie[crt][1], trie[pre][1], vpos, d - 1);
else update(trie[crt][0], trie[pre][0], vpos, d - 1);
}

void dfs(int crt) {
idx[crt] = ++node_size;
sz[crt] = 1;
update(root[idx[crt]], root[idx[crt] - 1], crt, SIZE);
for (int i = 0; i < adj[crt].size(); i++) {
}
}

int query(int lb, int rb, int x, int d, int res) {
if (d == NIL) return res;
int key = ((x >> d) & 1) ^ 1;
int isInRange = role[trie[rb][key]] - role[trie[lb][key]];
if (isInRange) return query(trie[lb][key], trie[rb][key], x, d - 1, res | (1 << d));
else return query(trie[lb][key ^ 1], trie[rb][key ^ 1], x, d - 1, res);
}

int main(void) {
int n, q;
while (~scanf("%d%d", &n, &q)) {
init(n);
for (int i = 1; i <= n; i++)
scanf("%d", values + i);
for (int i = 2; i <= n; i++) {
int p;
scanf("%d", &p);
}
dfs(1);
int u, x;
while (q--) {
scanf("%d%d", &u, &x);
printf("%d\n", query(root[idx[u] - 1], root[idx[u] + sz[u] - 1], x,  SIZE, 0));
}
}
}
```

https://www.cnblogs.com/Blackops/p/7493464.html

https://www.cnblogs.com/teble/p/8952322.html

https://blog.csdn.net/jinglinxiao/article/details/77803383