問題文
林戈有一条绳子。 我正在通过连接 N 气球来玩。气球 i (1 ≦ i ≦ N) 字符串的长度是 L_i 。林檎是一个气球 手握 1 绳子和气球 i (2 ≦ i ≦ N) 字符串到气球 P_i 我把它系上了。我们将这样的东西称为“气球树”,其中多个气球相连。
气球树的高度是气球树中包含的最高气球的高度。然而,气球 1 的高度是 L_1 和气球 i (2 ≦ i ≦ N) 的高度是一个气球 到 P_i 的高度 假设它是 L_i 的总和。
林戈想通过解开一些绳子来使气球树的高度与天花板完全相同。我还想知道为此目的需要解开的最少绳子数量。气球 当你解开 i (2 ≦ i ≦ N) 绳子时,它就变成了一个气球。 i 并且与其连接的所有气球都会飞走并从气球树上移除。
天花板高度的可能值为 由于有 Q 块,求最少需要解开多少根绳子才能使气球树的高度与天花板的高度完全相同。
入力
输入将以以下格式从标准输入给出。
N L_1 L_2 ... L_N P_2 P_3 ... P_N Q H_1 H_2 : H_Q
- 1 行包含一个表示气球数量的整数。 N (2 ≦ N ≦ 10^5) 给出。
- 2 行中,N 整数由空格分隔。其中 i (1 ≦ i ≦ N) 第一个整数 L_i (1 ≦ L_i ≦ 10^4) 是一个气球 i 表示字符串的长度。
- 3 行中,N-1 整数由空格分隔。其中 i (1 ≦ i ≦ N-1) 第一个整数 P_{i+1} (1 ≦ P_{i+1} ≦ i) 林戈是一个气球 i+1 字符串到气球 P_i 表示已附加。
- 4 行包含一个整数,表示可能的天花板高度数。 Q (1 ≦ Q ≦ 10^5) 给出。
- 5 从线 Q 行数过多 i (1 ≦ i ≦ Q) 行包含一个表示天花板高度的整数。 H_i (1 ≦ H_i ≦ 10^9) 给出。
出力
输出是 由 Q 行组成。其中 在 i (1≦i≦Q) 行中,将气球树的高度设置为 打印需要解开以形成 H_i 的字符串的最小数量。然而,仅仅 如果你不能这样做 H_i 输出 -1 。还在输出末尾添加换行符。
入力例1
5 1 1 2 2 2 1 2 2 1 2 2 3
出力例1
3 1
下图显示了初始气球树及其高度。 2 气球树,高度 3 这显示了气球树的样子。红色 x 标记表示应解开绳子的点。
入力例2
10 10 5 6 4 2 2 3 1 1 5 1 1 2 2 3 5 7 7 2 5 10 12 15 17 21
出力例2
2 -1 4 4 0