/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の整数列 A=(A_1,A_2,\cdots,A_N)，および長さ N-1 の整数列 P=(P_2,\cdots,P_N) が与えられます． P の添字が 2 から始まることに注意してください． また，1 \leq P_i<i が保証されます．
あなたは今から以下の操作を 10^{100} 回繰り返します．
- 各 i=2,\cdots,N について，この順に，A_{P_i} の値を A_{P_i}+A_{i} で置き換える．
すべての操作が終了したときの A_1 が 正, 負, 0 のいずれになるかを求めてください．
制約
- 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
出力
すべての操作が終了したときの A_1 が正である場合 + を出力せよ．
負である場合 - を出力せよ．
0 である場合 0 を出力せよ．
入力例 1
4 1 -2 3 -4 1 2 3
出力例 1
-
最初の数回の操作の結果を以下に示します．
- 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)
- 2 回目の操作後，A=(0,0,-5,-4) となる．
- 3 回目の操作後，A=(0,-5,-9,-4) となる．
- 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
+
Score : 400 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N, and another integer sequence P=(P_2,\cdots,P_N) of length N-1. Note that the index of P starts at 2. It is guaranteed that 1 \leq P_i < i for each i.
You will now repeat the following operation 10^{100} times.
- For each i=2,\cdots,N, in this order, replace the value of A_{P_i} with A_{P_i}+A_{i}.
Determine whether A_1 will be positive, negative, or zero when all operations are completed.
Constraints
- 2 \leq N \leq 250000
- -10^9 \leq A_i \leq 10^9
- 1 \leq P_i < i
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N P_2 \cdots P_N
Output
If A_1 is positive when all operations are completed, print +; if it is negative, print -; if it is zero, print 0.
Sample Input 1
4 1 -2 3 -4 1 2 3
Sample Output 1
-
Shown below are the results of the first few operations.
- After the first operation:
- Before the operation: A=(1,-2,3,-4).
- Processing for i=2: Replace the value of A_1 with A_1+A_2=1+(-2)=-1.
- Processing for i=3: Replace the value of A_2 with A_2+A_3=-2+3=1.
- Processing for i=4: Replace the value of A_3 with A_3+A_4=3+(-4)=-1.
- After the operation: A=(-1,1,-1,-4).
- After the second operation, A=(0,0,-5,-4).
- After the third operation, A=(0,-5,-9,-4).
- After the fourth operation, A=(-5,-14,-13,-4).
- \vdots
After 10^{100} operations, A_1 will be negative.
Thus, you should print -.
Sample Input 2
3 0 1 -1 1 1
Sample Output 2
0
Sample Input 3
5 1 -1 1 -1 1 1 1 2 2
Sample Output 3
+
Sample Input 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
Sample Output 4
+