[AdditionalFile5229.zip](file://AdditionalFile5229.zip?type=additional_file)

#5229. 「UOI 2021 Stage 4 Day1」树上的强盗

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2021 Stage 4 Day1 T4. Бандити на дереві

有 $n$ 座城市，编号从 $1$ 到 $n$。所有城市通过 $(n - 1)$ 条道路连接，形成一个连通图，任意两座城市之间都可以互相到达。每条道路都有一定的长度。

已知编号为 $i$ 的城市在时间 $t_i$ 被编号为 $a_i$ $(1 \leq a_i \leq n)$ 的强盗帮派占领。从城市 $i$ 被占领的时间 $t_i$ 开始（包括 $t_i$），只有 $a_i$ 帮派的成员可以通过这座城市。

请回答 $m$ 个查询，每个查询的形式如下：

• $u\ v\ b\ T$：编号为 $b$ 的帮派成员是否能在时间 $T$ 开始旅行时，从城市 $u$ 到达城市 $v$。如果无法完成旅行，还需要输出从 $u$ 到 $v$ 路径上第一个无法通过的城市编号。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 10^{5})$，表示城市的数量。

接下来的 $(n - 1)$ 行，每行包含两个整数 $p_i$ 和 $d_i$ $(1 \leq p_i < i, 1 \leq d_i \leq 10^{3})$，表示城市 $i$ 和城市 $p_i$ 之间有一条长度为 $d_i$ 的道路。注意索引从 $2$ 开始。

接下来的一行包含 $n$ 个整数 $a_i$ $(1 \leq a_i \leq n)$，表示占领对应城市的强盗帮派编号。

再接下来的一行包含 $n$ 个整数 $t_i$ $(1 \leq t_i \leq 10^{9})$，表示每座城市被占领的时间。

再接下来的一行包含一个整数 $m$ $(1 \leq m \leq 10^{5})$，表示查询的数量。

最后 $m$ 行描述查询，每行包含四个整数 $u_i, v_i, b_i, T_i$ $(1 \leq u_i, v_i, b_i \leq n, 1 \leq T_i \leq 10^{9})$，分别表示起始城市编号、目标城市编号、旅行者所属帮派编号以及旅行开始的时间。

输出格式

对每个查询，在单独的一行输出一个整数，表示从 $u$ 到 $v$ 路径上第一个无法通过的城市编号。如果不存在这样的城市，则输出 $\texttt{-1}$。

请注意本题输入输出数据量较大，建议使用高效的输入输出方式，例如在 C++ 中使用 $\texttt{scanf/printf}$ 而非 $\texttt{cin/cout}$，在 Python 中使用 $\texttt{sys.stdin.readline}$ 而非 $\texttt{input}$。同时，建议在 Python 中使用 PyPy 解释器来解决此问题。

样例 1

输入

5
1 7
1 3
2 2
2 1
1 1 2 3 3
10 4 15 15 1
8
5 3 3 1
5 3 3 2
5 3 3 3
5 3 1 1
4 3 1 2
4 3 1 3
3 4 1 3
2 1 1 100

输出

-1
1
2
5
-1
3
4
-1

样例 2

输入

5
1 4
1 1
1 1
1 4
3 2 2 2 2
4 4 6 7 5
5
5 2 4 7
1 1 1 3
4 2 1 9
1 4 3 7
3 4 2 4

输出

5
-1
4
4
1

样例 3

输入

5
1 4
2 1
3 3
4 1
2 1 2 3 2
8 3 7 7 9
5
1 5 2 4
1 2 1 4
5 2 1 6
1 4 3 5
1 5 4 7

输出

2
-1
4
2
2

数据范围与提示

详细子任务附加限制及分值如下表所示：