DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Deadly Assassins

Back to problem

Editorial

For every ai>0a_i>0ai​>0, regard aia_iai​ as the parent of iii. Since ai<ia_i<iai​<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 bvb_vbv​ be the number of living light children of vertex vvv, and let hhh be the alive state of its heavy child. If vvv has been hired, its alive state is 1−h1-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 000 or 111 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)O(\log N)O(logN) chains. A point update and a chain query each take O(log⁡N)O(\log N)O(logN). Add every chain's change in living count to the answer.

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

Solution written by GPT6

1
−
h
bv=0b_v=0bv​=0
000