33150번 - 나무핑

문제

처음에 1ドル$번 노드 하나로 이루어진 트리에 $Q$개의 쿼리를 적용하려 하며 $i$번째 쿼리는 다음과 같다.

• $q_i$ $w_i$: 새로운 $i + 1$번 노드와 트리의 $q_i$번 노드 사이를 $w_i$의 가중치를 가지는 간선으로 잇는다.

각 쿼리마다 노드를 추가한 후의 트리의 지름을 출력하라. 쿼리는 누적된다.

입력

첫 번째 줄에 쿼리의 개수 $Q$가 주어진다. $\left( 1 \le Q \le 200,000円\right)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리 $q_i,ドル $w_i$가 공백으로 구분되어 주어진다. $\left(1 \le q_i \le i; 0 \le w_i \le 10^{9}\right)$

출력

$Q$개의 줄에 걸쳐 각 쿼리마다 노드를 추가한 후의 트리의 지름을 출력한다.

쿼리는 누적됨에 유의하라.

제한

노트

트리에서 가장 먼 두 노드 간의 거리를 트리의 지름이라고 한다.