AT_arc169_a.[ARC169A] Please Sign

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $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$ 。

输入格式

输入通过标准输入按以下格式给出。

$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
```
-
```
输入#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

说明/提示

限制条件

$2\leq N\leq 250000$
$-10^9\leq A_i\leq 10^9$
$1\leq P_i < i$
所有输入值均为整数。

样例解释 1

以下展示了最初几次操作的结果。

第 $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$ 会变为负数。

因此，应输出 -。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页