시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 21 1 1 16.667%

문제

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번이 주어질 때 마다 순서대로 정답을 한 줄에 하나씩 출력한다.

예제 입력 1

4 6
1 0 2
2 1 1
3 2 3
2 2
1 3
2 2
2 3
2 1
1 3

예제 출력 1

0
3
0
4

예제 입력 2

4 5
1 0 5
2 1 6
3 0 4
2 2
1 0
1 3
2 2
2 3

예제 출력 2

0
26
4

예제 입력 3

8 8
1 0 1
2 0 3
3 2 3
4 0 1
5 2 0
6 5 1
7 1 0
1 7
2 4
1 3
1 5
1 5
1 4
2 0
2 6

예제 출력 3

2
11
15

출처