13431번 - 트리 문제

N개의 정점으로 이루어진 트리가 있다. 정점 번호는 0번부터 N-1번까지이다. 처음에, 트리의 모든 정점은 흰색이다. 이제 다음과 같은 Q개의 쿼리를 처리해야 한다.

• 쿼리 1: x번 정점을 파란색으로 색칠한다.
• 쿼리 2: x번 정점과 모든 파란 정점 사이의 거리의 합을 계산한다.

모든 쿼리 2의 정답을 구하는 프로그램을 작성하시오.

첫째 줄에 정점의 개수 N(2 ≤ N ≤ 100,000)과 쿼리의 개수 Q(1 ≤ Q ≤ 100,000)가 주어진다.

둘째 줄부터 N-1개의 줄에는 트리의 간선 정보 u, v, w가 주어진다. u와 v는 간선이 연결하는 두 정점이며, w는 간선의 길이이다. (1 ≤ w ≤ 1,000,003)

다음 Q개의 줄에는 쿼리의 정보가 주어진다. 첫 번째 정수는 쿼리의 종류 (1 또는 2)이며, 두 번째 정수는 쿼리의 x이다.

쿼리 2번이 주어질 때 마다 순서대로 정답을 한 줄에 하나씩 출력한다.