점멸 점검

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

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

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

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

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

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

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

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

• $1 \leq T \leq 150\,000$.
• $2 \leq N \leq 300\,000$.
• $S_i$ ().