DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Deadly Assassins

返回题目

题解

ai>0a_i>0ai​>0이면 iii에서 aia_iai​로 향하는 관계를 생각하자. ai<ia_i<iai​<i이므로 전체 관계는 루트가 여러 개인 포레스트이다. 정점 vvv가 살아 있는지는 살아 있는 자식의 수가 000인지로 결정된다.

전체 포레스트를 미리 알고 있으므로 HLD로 무거운 경로들로 나눈다. 한 정점 vvv의 가벼운 자식 중 살아 있는 수를 bvb_vbv​라 하고 무거운 자식의 생사를 hhh라 하자. vvv가 활성화되었다면 생사는 bv=0b_v=0일 때 , 그렇지 않을 때 이다. 아직 고용되지 않은 정점은 아무 영향도 주지 않는 항등 함수로 취급한다.

각 무거운 경로의 정점별 함수를 위에서 아래 순서로 세그먼트 트리에 놓는다. 구간마다 아래쪽 입력 생사 0,10,10,1 각각에 대해 위쪽 출력 생사와 그 구간의 생존자 수를 저장한다. 두 구간의 정보는 아래 구간의 출력을 위 구간의 입력으로 넣어 상수 시간에 합칠 수 있다.

새 정점 iii를 활성화하고 그 경로의 정보를 다시 구한다. 경로 머리의 생사가 달라지면 부모의 bvb_vbv​를 갱신하고 부모가 속한 경로로 전파한다. 머리의 생사가 같으면 더 위에는 영향이 없다. 각 전파는 가벼운 간선을 하나 지나므로 HLD 성질상 경로를 O(log⁡N)O(\log N)O(logN)개만 방문한다. 방문한 경로마다 세그먼트 트리 갱신과 구간 질의를 O(log⁡N)O(\log N)에 수행한다. 각 경로의 생존자 수 변화량을 전체 답에 더한다.

전체 시간 복잡도는 O(Nlog⁡2N)O(N\log^2 N)O(Nlog2N), 공간 복잡도는 O(N)O(N)O(N)이다. 서브태스크 111은 매 질의마다 현재 포레스트의 생사를 정점 번호 역순으로 다시 계산할 수 있다.

Solution written by GPT6

bv​
=
0
1−h1-h1−h
000
O(logN)