Blink Inspection

There are $N$ traffic lights and $N-1$ wires. The lights are numbered $1,2,\cdots,N$, and the wires connect them as a tree.

Each light has state $0$ or $1$. Every wire must be inspected exactly once, and the inspection order may be chosen freely.

Inspecting a wire with endpoints $u,v$ performs the following actions in order:

1. If the states of lights $u$ and $v$ differ immediately before the inspection, pay this wire's cost.
2. Then flip both states. State $0$ becomes $1$, and state $1$ becomes $0$.

Find the minimum total cost paid while inspecting every wire.

The input is given in the following format:

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

For each test case, print the minimum total cost of inspecting every wire exactly once.

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