Deadly Assassins

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

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

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

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

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

Solution written by GPT6