점멸 점검

전역 점검 순서에서 간선 $e$보다 먼저 점검된, 정점 $v$에 연결된 간선 수의 홀짝을 $x_{v,e}$라 하자. 간선 $e=uv$에서 비용이 발생할 필요충분조건은

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

이다.

차수가 $d$인 정점에서 연결된 간선의 국소 순위는 $0,1,\cdots,d-1$이다. 따라서 정확히 $\lfloor d/2\rfloor$개의 incidence가 $x_{v,e}=1$을 가진다. 반대로 임의의 $\lfloor d/2\rfloor$개를 국소 순서의 두 번째, 네 번째, $\cdots$ 위치에 놓을 수 있다.

트리에서는 정점마다 정한 임의의 국소 간선 순서들이 항상 하나의 전역 순서로 합쳐진다. 각 정점의 국소 선후관계를 합친 방향 그래프에 사이클이 있다면, 트리의 선 그래프 구조상 그 사이클은 한 정점에 대응하는 완전그래프 안에 있어야 한다. 그러나 그 완전그래프의 방향은 하나의 선형 순서에서 왔으므로 사이클이 없다.

따라서 문제는 각 정점 $v$에서 정확히

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

개의 incidence를 $1$로 고르는 정적 최적화가 된다.

트리를 루팅한다. 부모 간선의 $v$ 쪽 값이 $p$일 때 서브트리 최소 비용을 $\mathrm{dp}[v][p]$라 하자. 자식 $w$와의 간선 $e$에서 $v$ 쪽 값을 $a$로 정했을 때의 최적 비용을

$$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)$$

로 둔다. 모든 자식에서 $a=0$을 선택한 비용에 $\Delta_e=G_e(1)-G_e(0)$가 가장 작은 $q_v-p$개를 더하면 된다.

각 정점에서 $\Delta$를 정렬한다. 전체 시간 복잡도는 $O(N\log N)$이고 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5