本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-12-12 22:54:59

题意

给定整数列 $A(A_1, A_2, \cdots, A_N)$ 与 $P(P_2, P_3, \cdots, P_N)$ ($1 \leq P_i \leq i$).

有以下操作：

• 对 $i = 2, \cdots,N$，将 $A_{P_i}$ 加上 $A_i$

重复以上操作 $10^{100}$ 次，问 $A_i$ 正负性。

分析

根据样例 1 有推导：

第一次操作后： $$ \begin{aligned} A_1 = A_i + A_2 \ A_2 = A_2 + A_3 \ A_3 = A_3 + A_4 \ A_4 = A_4 \end{aligned} $$

第二次操作后： $$\begin{aligned} A_1 = A_1 + A_2 = A_1 + 2A_2 + A_3 \ A_2 = A_2 + 2A_3 + A_4 \ A_3 = A_3 + 2A_4 \ A_4 = A_4 \end{aligned}$$

第三次操作后： $$\begin{aligned} A_1 = A_1 + 3A_2 + 3A_3 + A_4 \ A_2 = A_2 + 3A_3 + 3A_4 \ A_3 = A_3 + 3A_4 \end{aligned}$$

第 $10^{100}$ 次（在本问题下可以看作趋向正无穷）操作后： $$\begin{aligned} \lim_{n\rightarrow \infty} A_1 = n\times A_2 \ \lim_{n\rightarrow \infty} A_2 = n \times A_3 \ \lim_{n\rightarrow \infty} A_3 = n\times A_4 \end{aligned} $$ 显然，$A_3$ 的正负性由 $A_4$ 决定。同理 $A_2$ 的正负性由 $A_3$ 决定，$A_1$ 的正负性便是由 $A_2$ 决定。

于是确定 $A_1$ 的正负性就变成了从 $A_n$ 开始向上的一条推导的长链。

但是我们需要考虑 $P$ 值重复，例如 $A_2 = A_2 + A_3 + A_4$ 的情况。实际上这并不是问题，因为很明显可以将 $A_3 + A_4$ 视作整体处理。

因此我们的策略便是，构建出一颗以 $1$ 为根的树，从下到上推导每一层的正负性，低一层的正负性决定更高一层的。