#341 서브트리의 최소 길이합

Statement

가중치가 있는 트리 $T$ 가 주어진다. 트리는 $1$ 번부터 $N$ 번까지 번호가 붙은 $N$ 개의 정점과 $N-1$ 개의 간선으로 이루어져 있다.

처음에는 주요 정점이 하나도 없다. 이후 $Q$ 개의 사건이 순서대로 주어진다. 사건의 형태는 다음 두 가지 중 하나이다.

$1\ v$ : 정점 $v$ 의 상태를 바꾼다. 정점 $v$ 가 주요 정점이 아니었다면 주요 정점이 되고, 주요 정점이었다면 주요 정점이 아니게 된다.
$2$ : 현재 모든 주요 정점을 포함하는 연결 부분그래프 중, 포함된 간선 길이의 합이 최소인 것의 값을 출력한다.

주요 정점이 $0$ 개 또는 $1$ 개라면 사건 $2$ 의 답은 $0$ 이다.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $u_1\ v_1\ w_1$ $u_2\ v_2\ w_2$ $\vdots$ $u_{N-1}\ v_{N-1}\ w_{N-1}$ $\mathrm{event}_1$ $\mathrm{event}_2$ $\vdots$ $\mathrm{event}_Q$

각 $i$ ( $1 \leq i \leq N-1$ )에 대해 $i$ 번 간선은 정점 $u_i$ 와 정점 $v_i$ 를 잇고, 길이는 $w_i$ 이다.

각 사건은 한 줄에 하나씩 주어지며, $1\ v$ 또는 $2$ 형태이다.

사건 $2$ 가 주어질 때마다 정답을 한 줄에 하나씩 출력한다.

입력

출력

처음에는 주요 정점이 없으므로 첫 번째 출력은 $0$ 이다.

정점 $4$ 만 주요 정점인 경우에도 필요한 간선이 없으므로 답은 $0$ 이다.

정점 $4$ 와 정점 $5$ 가 주요 정점인 경우 두 정점을 잇는 경로의 길이가 $4+1=5$ 이므로 답은 $5$ 이다.

이후 사건들도 같은 방식으로 현재 주요 정점들을 모두 포함하는 연결 부분그래프의 최소 간선 길이 합을 출력한다.