Blink Inspection

For an incidence of vertex $v$ and edge $e$, let $x_{v,e}$ be the parity of the number of edges incident to $v$ that were inspected before $e$. Edge $e=uv$ incurs its cost exactly when

$$S_u\mathbin{\mathrm{XOR}}S_v\mathbin{\mathrm{XOR}}x_{u,e}\mathbin{\mathrm{XOR}}x_{v,e}=1.$$

At a vertex of degree $d$, local ranks are $0,1,\cdots,d-1$, so exactly $\lfloor d/2\rfloor$ incidences have value $1$. Conversely, any chosen $\lfloor d/2\rfloor$ incident edges can occupy the second, fourth, and later even positions.

For a tree, arbitrary local edge orders at all vertices can always be merged into one global order. If the union of all local precedence constraints contained a directed cycle, the line-graph structure of a tree would force that cycle to lie inside the clique belonging to one original vertex. That clique is oriented by a linear order and is acyclic, a contradiction.

The problem is therefore a static optimization: at every vertex $v$, choose exactly

$$q_v=\left\lfloor\frac{\deg(v)}2\right\rfloor$$

incidences with value $1$.

Root the tree. Let $\mathrm{dp}[v][p]$ be the minimum subtree cost when the value on $v$'s side of its parent edge is $p$. For a child $w$ joined by edge $e$, if the value on $v$'s side is $a$, define

$$G_e(a)=\min_{b\in\{0,1\}}\left(\mathrm{dp}[w][b]+C_e[S_v\mathbin{\mathrm{XOR}}S_w\mathbin{\mathrm{XOR}}a\mathbin{\mathrm{XOR}}b=1]\right).$$

Start with $a=0$ for every child. Then add the smallest $q_v-p$ values of $\Delta_e=G_e(1)-G_e(0)$.

Sorting the deltas at every vertex gives $O(N\log N)$ time and $O(N)$ memory.

Solution written by GPT5