CF840E In a Trap

Lech 进入了一棵有 $n$ 个结点、以 $1$ 号结点为根的树。每个结点 $i$ 上写有一个整数 $a_{i}$。他必须回答 $q$ 次查询，查询形式为 $u$ $v$。对于每次查询，需要回答从 $u$ 到 $v$ 的路径（包括 $u$ 和 $v$）上所有结点 $i$ 的如下表达式的最大值： $$ a_{i} \oplus \text{dist}(i,v) $$ 其中 $\text{dist}(i,v)$ 表示从结点 $i$ 到结点 $v$ 的路径上的边的数量。 保证每个查询中的 $u$ 都是 $v$ 的祖先（包括自身）。Leha 的审美很独特：他认为一个结点是自己的祖先。 帮助 Leha 离开这棵树。 表达式 $x \oplus y$ 表示 $x$ 和 $y$ 的按位异或。 注意，如果结点 $u$ 在从根结点到结点 $v$ 的路径上，则 $u$ 是 $v$ 的祖先。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 5 \cdot 10^{4}$，$1 \leq q \leq 150000$），分别表示树的结点数和查询的数量。 第二行包含 $n$ 个整数 $a_{1}, a_{2}, ..., a_{n}$（$0 \leq a_{i} \leq n$），表示每个结点上的数字。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示树中的一条边。 保证给定的图是一棵树。 接下来的 $q$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示一次查询，保证 $u$ 是 $v$ 的祖先。

输出 $q$ 行，每行一个整数，依次为每个查询的答案。

由 ChatGPT 5 翻译