12023번 - 연세대학교 포인트 게임

올 해 2학년이 된 연돌이는 새로운 신입생들을 맞아 오티에서 사용할 교내 포인트게임을 담당하게 되었다. 포인트 게임이란 교내 곳곳에 있는 시설 위치에 익숙해지기 위해 각각의 위치에서 미션을 수행하는 게임이다. 보통 해당 위치에 가서 미션을 수행하고 다음 위치로 이동하는 형태로 진행되나, 작년에 포인트 게임에 참가했었던 연돌이는 이와 같은 형태의 포인트 게임이 가지는 한계점에 대해서 고민하고 있었다. 한 번 방문한 장소에 다시는 방문하지 않기 때문에 실질적으로 위치 암기에는 그다지 도움이 되지 않았던 것이다.

이와 같은 문제를 해결하기 위해 연돌이는 새로운 포인트 게임을 고안해 내었다. 새로운 포인트 게임의 규칙은 다음과 같다:

교내 N 곳의 장소에 대하여 포인트 게임을 진행하고, N 곳의 장소는 트리 형태로 연결되어 있다. (N곳은 N – 1 개의 두 장소를 잇는 도로를 통해서 결과적으로 모두 연결되어 있으며, 각 도로는 양방향성이고 사이클이 없다). 각 도로의 길이는 다를 수 있다.

이때 Q번의 미션을 수행해야 하며 수행해야 하는 미션의 종류는 2 종류인데,

1. 주어진 장소 A에 방문해 파란 락커를 칠한다
2. 주어진 장소 A로부터 모든 파란 락커가 칠해진 곳까지의 길이의 합을 구한다.

이다. 처음 시작할 때 모든 장소는 락커가 칠해져 있지 않다.

과거 방문했던 장소에 대해서도 지속적으로 알아야 하는 게임이기에 시설 위치 숙달에 좀 더 도움이 되는 게임이지만, 아뿔싸 게임이 너무 어려운 나머지 연돌이도 2번 미션들에 대한 답들을 알 수가 없었다. 당신은 우수한 프로그래머로써 연돌이를 도와 포인트 게임을 성공적으로 진행시켜야 한다!

데이터의 첫 줄에는 장소의 개수 N(1 <= N <= 100,000)이 주어지며, 장소는 각각 0 ~ N – 1로 숫자를 매겨 부른다.

이어지는 1 ~ N – 1 줄에 걸쳐서 장소들의 연결 정보가 들어오며, 각 i번째 줄에 대하여 두 정수 Ai, Bi(0 <= Ai < i, 1 <= Bi <= 100)가 입력된다. 이는 장소 i가 장소 Ai와 거리 Bi의 도로로 연결되어 있음을 나타낸다.

이어서 미션의 개수 Q(1 <= Q <= 100,000)이 한 줄에 걸쳐 주어진다.

이어서 Q 줄에 걸쳐 정수 Ci, Di (Ci = 1 or 2, 0 <= Di < N)이 주어지며, 각 줄은 수행해야 하는 미션들을 순서대로 써 놓은 것이다. Ci = 1일 경우 Di번째 장소에 락커를 칠해야 하고, Ci = 2일 경우 여태까지 칠한 락커 정보를 바탕으로 Di번째에서 모든 락커가 칠해진 장소까지의 길이의 합을 구해서 출력해야 한다.