题目描述

有 $n$ 个城市，编号从 $1$ 到 $n$。所有城市通过 $n-1$ 条道路连接，形成一个连通图。每条道路都有特定的长度。

已知编号为 $i$ 的城市在时间 $t_i$ 被编号为 $a_i$ 的强盗团伙占领（$1 \leq a_i \leq n$）。从被占领的时刻 $t_i$ 开始（包括 $t_i$ 时刻），只有 $a_i$ 号团伙的成员才能通过该城市。

你需要回答 $m$ 个如下形式的查询：

• u v b T：判断编号为 $b$ 的团伙成员能否在时间 $T$ 从城市 $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$），分别表示查询的起点城市、终点城市、团伙编号和出发时间。

输出格式

对于每个查询，输出一行一个整数——路径上第一个无法通过的城市编号。如果全程可通行，输出 -1。

注意本题输入输出数据量较大，建议使用快速的输入输出方法，例如：

• C++ 中使用 scanf/printf 而非 cin/cout；
• Python 中使用 sys.stdin.readline 而非 input；
• 建议使用 PyPy 解释器运行 Python 代码。

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

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

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

提示

评分标准

1. （$7$ 分）：所有 $p_i = 1$；
2. （$9$ 分）：$n, m \leq 10^3$；
3. （$11$ 分）：$p_i = i-1$，$t_i = 1$；
4. （$18$ 分）：$p_i = i-1$，$a_i = 1$，$b_i = 2$；
5. （$15$ 分）：$p_i = i-1$；
6. （$11$ 分）：$t_i = 1$；
7. （$17$ 分）：$a_i = 1$，$b_i = 2$；
8. （$12$ 分）：无额外限制。

翻译由 DeepSeek V3 完成