점멸 점검

$N$개의 신호등과 $N-1$개의 전선이 있다. 신호등은 $1,2,\cdots,N$번이며, 전선은 모든 신호등을 하나의 트리 형태로 연결한다.

각 신호등의 상태는 $0$ 또는 $1$이다. 모든 전선을 정확히 한 번씩 점검해야 하며, 점검 순서는 자유롭게 정할 수 있다.

양 끝점이 $u,v$인 전선을 점검하면 다음 일이 순서대로 일어난다.

1. 점검 직전 신호등 $u$와 $v$의 상태가 서로 다르면 이 전선의 비용을 지불한다.
2. 그 뒤 신호등 $u$와 $v$의 상태를 모두 반전한다. 즉, $0$은 $1$이 되고 $1$은 $0$이 된다.

모든 전선을 점검할 때 지불하는 비용 합의 최솟값을 구하여라.

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

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $S$ $u_1\ v_1\ C_1$ $u_2\ v_2\ C_2$ $\vdots$ $u_{N-1}\ v_{N-1}\ C_{N-1}$

$S_i$는 $i$번 신호등의 초기 상태를 나타낸다.

각 테스트 케이스마다 모든 전선을 정확히 한 번씩 점검할 때 지불하는 비용 합의 최솟값을 한 줄에 출력한다.

• $1 \leq T \leq 150\,000$.
• $2 \leq N \leq 300\,000$.
• $S_i\in\{0,1\}$ ($1 \leq i \leq N$).
• $1 \leq u_i,v_i \leq N$, $u_i\neq v_i$ ($1 \leq i \leq N-1$).
• $1 \leq C_i \leq 10^9$ ($1 \leq i \leq N-1$).
• 주어진 전선은 트리를 이룬다.
• 모든 테스트 케이스에 대한 $N$의 합은 $300\,000$ 이하이다.