35111번 - 제목은 나무 키우기로 하겠습니다. 근데 이제 삼각형을 곁들인

코코아는 셰익고등학교에 재학 중인 학생이다. 이번 겨울방학 동안 그녀는 트리 관찰 일지를 작성하는 숙제를 하게 되었다. 그녀는 총 $N$일에 걸쳐 $1$번 정점을 루트로 하는 트리 $T$를 키우며 관찰 일지를 작성할 것이다.

• $1$일차에 $T$는 양의 정수 가중치 $A_1$을 가진 $1$번 정점 하나로 구성되어 있다.
• $2 \le i \le N$을 만족하는 모든 $i$에 대해 $i-1$일차에서 $i$일차로 날짜가 바뀌는 순간, $i$번 정점이 새로 자라난다. 이 정점은 현재 존재하는 정점 $p_i$와 연결되어 자라나며 양의 정수 가중치 $A_i$를 가진다.

$T$의 어떤 정점 $v$가 흥미롭다는 것은, 정점 $v$의 서브트리에 서로 다른 세 정점 $i$, $j$, $k$가 존재하여 $A_i$, $A_j$, $A_k$를 세 변의 길이로 하는 삼각형을 만들 수 있다는 것과 같다.

코코아의 선생님인 모카는 코코아가 매일 $T$에 존재하는 흥미로운 정점의 개수를 구하여 관찰 일지에 기록할 것을 요구했다. 유감스럽게도 코코아는 국제 바리스타 변호사가 되기 위한 공부를 하느라 숙제할 시간이 없다. 코코아를 위해 모든 $2 \le i \le N$에 대해 $i$일차 아침에 $T$에 존재하는 흥미로운 정점의 개수를 구해보자.

첫 번째 줄에는 양의 정수 $N$이 주어진다. $(2\le N\le 100\,000)$

두 번째 줄에는 양의 정수 $A_1$이 주어지며, 이는 $1$번 정점의 가중치를 의미한다. $\left(1\le A_i\le 10^9\right)$

이후 $N-1$개의 줄에 걸쳐 트리의 성장에 관한 정보가 주어진다. 그중 $i$번째 줄에는 $p_{i+1},A_{i+1}$가 공백으로 구분되어 주어진다. 이는 ${i+1}$번 정점이 $p_{i+1}$번 정점과 연결되어 자라나며, 그 가중치가 $A_{i+1}$이라는 의미이다. $(1\leq p_{i+1} \leq i)$

$N-1$개의 줄에 걸쳐, $i$번째 줄에는 $i+1$일차 아침에 존재하는 흥미로운 정점의 개수를 출력한다.