CF1479D Odd Mineral Resource

在 Homer 的国家里，有 $n$ 个城市，编号为 $1$ 到 $n$，这些城市构成一棵树。也就是说，这 $n$ 个城市之间有 $n-1$ 条无向道路，并且任意两个城市都可以通过这些道路互相到达。 Homer 的国家是一个工业国家，每个城市都蕴藏着一种矿产资源。城市 $i$ 的矿产资源编号为 $a_i$。 Homer 得到了接下来 $q$ 年的国家规划。第 $i$ 年的规划由四个参数 $u_i, v_i, l_i, r_i$ 描述，他需要找到一个矿产资源 $c_i$，使得以下两个条件同时成立： - 矿产资源 $c_i$ 在城市 $u_i$ 到城市 $v_i$ 的路径上出现了奇数次； - $l_i \leq c_i \leq r_i$。 作为 Homer 最好的朋友，他向你求助。对于每一年的规划，请你帮他找到任意一个满足条件的矿产资源 $c_i$，或者告诉他不存在这样的矿产资源。

第一行包含两个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）和 $q$（$1 \leq q \leq 3 \cdot 10^5$），分别表示城市数量和规划数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。 接下来的 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$，$x_i \neq y_i$），表示城市 $x_i$ 和城市 $y_i$ 之间有一条双向道路。保证这些道路构成一棵树。 接下来的 $q$ 行，每行包含四个整数 $u_i, v_i, l_i, r_i$（$1 \leq u_i \leq n$，$1 \leq v_i \leq n$，$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 年的规划。

输出 $q$ 行，第 $i$ 行输出一个整数 $c_i$，满足： - 如果不存在满足条件的矿产资源，则 $c_i = -1$； - 否则 $c_i$ 是第 $i$ 年选择的矿产资源编号，且满足上述条件。如果有多个可选的 $c_i$，输出其中任意一个即可。

在前三个询问中，城市 $3$ 到城市 $5$ 之间有四个城市，分别是城市 $1$、城市 $2$、城市 $3$ 和城市 $5$。它们的矿产资源分别为 $1$（出现在城市 $3$ 和城市 $5$）、$2$（出现在城市 $2$）、$3$（出现在城市 $1$）。注意： - 第一个询问只需判断矿产资源 $1$ 是否在城市 $3$ 到城市 $5$ 的路径上出现了奇数次。答案是否，因为矿产资源 $1$ 出现了两次（偶数次）。 - 第二个和第三个询问是一样的，但可以选择不同的矿产资源。矿产资源 $2$ 和 $3$ 都是可选的。 由 ChatGPT 4.1 翻译