카운터스펠

카드 게임 Magic: The Gathering에는 주문을 시전하고 상쇄하는 규칙이 있다. 아래 색칠 규칙은 여기에서 따왔다. 카드 게임 자체는 설명하지 않으며, 문제를 푸는 데 알 필요도 없다.

뿌리 있는 트리마다 다음 조건을 만족하도록 정점을 검은색과 흰색으로 칠하는 방법이 정확히 하나 있다.

• 정점이 흰색인 것은 그 정점에 검은색 자식이 있는 경우, 그리고 그 경우뿐이다.

색칠이 유일하다는 사실은 귀납법으로 쉽게 증명할 수 있다. 이렇게 칠한 트리를 잘 칠한 트리라고 부른다.

검은색 정점 하나로 이루어진 트리에서 시작한다. 이 정점이 뿌리이다. 여기에 다음 연산을 $n$번 수행한다.

• $add(v)$: 정점 $v$의 자식으로 새로운 검은색 정점을 붙인다. 그다음 트리가 다시 잘 칠한 트리가 되도록 정점 몇 개의 색을 반전시킨다. 하나도 반전시키지 않을 수도 있고, 전부 반전시킬 수도 있다.

각 연산에서 색이 반전되는 정점이 몇 개인지 구하라.

뿌리의 번호는 $0$이고, 나머지 정점은 트리에 추가되는 순서대로 $1, 2, \dots, n$번을 받는다.

첫째 줄에 정점을 추가하는 횟수 $n$이 주어진다. ($1 \le n \le 200000$)

다음 $n$개 줄 중 $i$번째 줄에는 $i$번째 연산에서 추가하는 정점의 부모 번호 $v_i$가 주어진다. 정점 $v_i$는 $i$번째 연산 전에 이미 존재한다. 즉, $v_i < i$이다.

$n$개 줄을 출력한다. $i$번째 줄에는 $i$번째 연산에서 색이 반전되는 정점의 개수를 출력한다. 그 연산에서 새로 붙인 정점은 검은색으로 붙었고 잎은 항상 검은색이므로, 반전되는 정점에 들어가지 않는다.

아래 그림은 첫 번째 예제의 시작 트리와 각 연산을 마친 뒤의 트리이다. 그 연산에서 색이 반전된 정점을 빨간 테두리로 표시했다.