分数: 400 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N,以及另一个整数序列 P=(P_2,\cdots,P_N) 长度 N-1。请注意,索引 P 开始于 2。可以保证 1 \leq P_i < i 对于每个 i.
您现在将重复以下操作 10^{100} 次。
- 对于每个 i=2,\cdots,N,按此顺序替换值 当所有操作完成时, A_{P_i} 与 A_{P_i}+A_{i}.
判断是否 A_1 将为正、负或零。 当所有操作完成后
约束
- 2 \leq N \leq 250000
- -10^9 \leq A_i \leq 10^9
- 1 \leq P_i < i
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N P_2 \cdots P_N
输出
If A_1 为正,打印 +;如果为负数,则打印 -;如果为零,则打印 0.
示例输入 1
4 1 -2 3 -4 1 2 3
示例输出 1
-
下面显示的是前几次操作的结果。
- 第一次操作后:
- 操作前: A=(1,-2,3,-4).
- 处理 i=2:替换的值 A_1 与 A_1+A_2=1+(-2)=-1.
- 处理 i=3:替换的值 A_2 与 A_2+A_3=-2+3=1.
- 处理 i=4:替换的值 A_3 与 A_3+A_4=3+(-4)=-1.
- 操作后: A=(-1,1,-1,-4).
- 第二次操作后, A=(0,0,-5,-4).
- 第三次操作后, A=(0,-5,-9,-4).
- 第四次操作后, A=(-5,-14,-13,-4).
- \vdots
之后 10^{100} 操作, A_1 将为负。
因此,您应该打印 -.
示例输入 2
3 0 1 -1 1 1
示例输出 2
0
示例输入 3
5 1 -1 1 -1 1 1 1 2 2
示例输出 3
+
示例输入 4
20 568273618 939017124 -32990462 -906026662 403558381 -811698210 56805591 0 436005733 -303345804 96409976 179069924 0 0 0 -626752087 569946496 0 0 0 1 1 1 4 4 6 7 2 2 3 3 8 13 14 9 9 15 18 19
示例输出 4
+