Deadly Assassins

For every $a_i>0$, regard $a_i$ as the parent of $i$. Since $a_i<i$, these relations form a rooted forest. A vertex is alive exactly when it has no living child.

The entire forest is known from the input, so apply HLD. Let $b_v$ be the number of living light children of vertex $v$, and let $h$ be the alive state of its heavy child. If $v$ has been hired, its alive state is $1-h$ when , and otherwise. An unhired vertex acts as an identity function with no contribution to the living count.

Place these functions along each heavy chain in a segment tree. For each possible input state $0$ or $1$ from below, a segment stores its output state at the top and the number of living vertices inside. Combine adjacent segments by feeding the lower segment's output into the upper segment. This takes constant time.

Activate a newly hired vertex and recompute its chain. If the chain head's state changes, update its parent's count of living light children and continue in the parent's chain. If the head state stays the same, nothing above changes. Each propagation crosses one light edge, so HLD visits only $O(\log N)$ chains. A point update and a chain query each take $O(\log N)$. Add every chain's change in living count to the answer.

The total time complexity is $O(N\log^2 N)$ and the space complexity is $O(N)$. For subtask $1$, recompute every currently hired vertex in descending number order after each query.

Solution written by GPT6