# 描述

Monkey A lives on a tree, he always plays on this tree.

One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once.

Monkey A gave a value to each node on the tree. And he was curious about a problem.

The problem is how large the xor result of number $x$ and one node value of label $y$ can be, when giving you a non-negative integer $x$ and a node label $u$ indicates that node $y$ is in the subtree whose root is $u$(y can be equal to $u$).

Can you help him?

## Input

There are no more than $6$ test cases.

For each test case there are two positive integers $n$ and $q$, indicate that the tree has $n$ nodes and you need to answer $q$ queries.

Then two lines follow.
The first line contains $n$ non-negative integers $V_1,V_2,⋯,V_n$, indicating the value of node $i$.
The second line contains $n-1$ non-negative integers $F_1,F_2,…F_{n−1}$, $F_i$ means the father of node $i+1$.

And then $q$ lines follow.
In the $i$-th line, there are two integers $u$ and $x$, indicating that the node you pick should be in the subtree of $u$, and $x$ has been described in the problem.
$2≤n,q≤10 ^ 5$
$0≤V_i≤10 ^ 9$
$1≤F_i≤n$, the root of the tree is node $1$.
$1≤u≤n,0≤x≤10 ^ 9$

## Output

For each query, just print an integer in a line indicating the largest result.

# 思路

• 先在树上跑一遍dfs序转为线性结构，然后问题就转变为在一个区间内选择一个数$s$与$x$的异或值最大。
• 用Trie来维护区间内每个数的每一位，然后在Trie上贪心查询即可（即尽量取和当前位不一样的值）
• 但是要对付这么多查询，我们不能每次都建一个Trie，所以考虑用莫队离线。
• 比较坑的地方就在于莫队中的删除操作，由于某个前缀（甚至某个数）可能出现多次，所以要在Trie中记录每个结点的访问次数，删除的时候仅减1！（因为这个错了好几次）
• 这题也可以使用启发式合并，维护每个点的子树，把询问离线对应到树上每个点即可。（不会0.0）

• 跑完dfs序后，按dfs序建可持久化字典树，维护dfs序前$x$个中每个数的出现次数，这样每次版本更新的时候只会更新（新增）$\log(v)$个结点，其他结点都可以继承上一个版本的信息。
• 然后查询的时候只要sz[out[u]]-sz[in[u]-1]>0就说明可以走这个点，贪心即可。

0%