\(i \to P_i \to P_{P_i} \to \cdots\) と繰り返すといつか \(1\) にたどり着きますが，ここで必要な \(\to\) の個数を \(i\) の深さ \(d_i\) と呼ぶことにします．

各 \(j\) \((0 \leq j < N)\)に対し，\(d_i=j\) となるすべての \(i\) について \(A_i\) の和をとった値を \(B_j\) と呼ぶことにします．

まず，\(A_1=B_0\) です． また，\(1\) 回の操作は，\(B_{j} \mathrel{+}=B_{j+1}\) (\(0 \leq j < N-1\))と表現できます．

すべての \(B_j\) が \(0\) だった場合，何度操作しても \(B_0=0\) のままなので，答えは 0 です．

非 \(0\) の \(B_j\) が存在したとします． ここで，\(B_j \neq 0\) なる最大の \(j\) をとり，\(k\) とおきます．

\(B_k>0\) の場合を考えてみます． まず \(B_j\) (\(j>k\)) はすべて \(0\) なので \(B_k\) の値は一定です． 特に，常に正です． 次に \(B_{k-1}\) について考えます．この値は操作の度に \(B_k\) 増えるので，初期値が負の値であっても十分な回数の操作のあとはずっと正になります． 次に \(B_{k-2}\) について考えます． まず先程の議論より，十分な回数の操作のあとは \(B_{k-1}\) は常に正です． この \(B_{k-1}\) が \(B_{k-2}\) に足されていくので，結局 \(B_{k-2}\) もいつかは正になります． このような議論を繰り返すと，結局，十分な回数操作したあとは \(B_0\) まで正になるとわかります． よってこの場合は + が答えになります．

\(B_k<0\) が負の場合も全く同様の議論で答えが - だとわかります．

ここでは十分な回数という表現を利用しましたが，きちんと計算すると \(10^{100}\) が十分であることがわかります． 二項係数を使って各 \(A_i\) の寄与を計算するとよいですが，ここでは詳細は省略します．

上記の判定をそのまま実装すれば \(O(N)\) 時間でこの問題は解けます．

解答例