← 返回题目列表

Codeforces · 1479/D

D. 奇怪的矿产资源

中文机器翻译题面 查看原题

在荷马的国家,有 $$$n$$$ 个城市,编号为 $$$1$$$ 到 $$$n$$$,它们形成一棵树。也就是说,这$$$n$$$个城市之间有$$$(n-1)$$$条无向道路,每两个城市可以通过这些道路相互到达。

荷马的国家是一个工业国家,其中的每个$$$n$$$城市都蕴藏着一定的矿产资源。城市 $$$i$$$ 的矿产资源标记为 $$$a_i$$$。

荷马获得了该国未来 $$$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$$$。

作为荷马最好的朋友,他向你寻求帮助。对于每个计划,找到任何此类矿物资源 $$$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)$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) 和 $$$x_i \neq y_i$$$,表示城市之间有一条双向道路$$$x_i$$$ 和城市 $$$y_i$$$。保证给定的道路形成一棵树。

那么接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含四个整数 $$$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$$$ 应满足问题陈述中上述第 $$$i$$$ 年的条件。如果 $$$c_i$$$ 有多个选择,则可以打印其中任何一个。

示例

输入 #1

6 8
3 2 1 3 1 3
1 2
1 3
2 4
2 5
4 6
3 5 1 1
3 5 1 3
3 5 1 3
1 1 2 2
1 1 3 3
1 4 1 5
1 6 1 3
1 6 1 3

输出 #1

-1
2
3
-1
3
2
2
3

注意

在前三个查询中,city $$$3$$$ 和 city $$$5$$$ 之间有四个城市,分别是 city $$$1$$$、city $$$2$$$、city $$$3$$$ 和 city $$$5$$$。其中出现的矿产资源为矿产资源$$$1$$$(出现在城市$$$3$$$和城市$$$5$$$)、$$$2$$$(出现在城市$$$2$$$)和$$$3$$$(出现在城市$$$1$$$)。值得注意的是

- 第一个查询仅检查矿源$$$1$$$在城市$$$3$$$和城市$$$5$$$之间是否出现奇数次。答案是否定的,因为矿源$$$1$$$在城市$$$3$$$和城市$$$5$$$之间出现了两次(偶数次)。
- 第二个和第三个查询相同,但可以选择不同的矿产资源。矿产资源 $$$2$$$ 和 $$$3$$$ 均可用。