P12577 [UOI 2021] 树上的强盗

有 $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 代码。

### 评分标准 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 完成