Exploration Records

트리를 $1$번 정점을 루트로 두고, $d_v$를 정점 $v$의 깊이, $p_v=d_v\bmod 2$라 하자.

로봇이 $u$에서 출발할 때의 배터리가 $C$이고 경로 위의 정점 $x$에 도착했다면, 그때의 배터리는

$$C+H_u-H_x$$

이다. 따라서 $u$와 $v$ 사이 경로의 최대 높이를 $H_{\max}$라 하면

$$A(u,v)=H_{\max}-H_u,\qquad B(u,v)=H_{\max}-H_v$$

이고, $Z(u,v)$는 $u$에서 $v$로 이동하는 순서에서 높이 $H_{\max}$를 처음 갖는 정점이다.

간선을 지날 때 높이가 정확히 $1$ 변하고 $H_1=0$이므로

$$H_v\equiv d_v\pmod 2$$

이다. 다음 정수 변수를 정의하자.

$$K_v=\frac{H_v-p_v}{2}.$$

그러면 $H_v=2K_v+p_v$이고 이다.

부모가 $q$, 자식이 $c$인 간선은 다음 두 차분 제약과 동치이다.

$$K_c-K_q\le p_q,\qquad K_q-K_c\le1-p_q.$$

기록 $(u,v,a,b,z)$를 생각하자. 먼저 $z$가 $u$와 $v$ 사이 경로 위에 있어야 한다.

$H_z-H_u=a$, $H_z-H_v=b$이므로

$$2(K_z-K_u)=a+p_u-p_z,$$ $$2(K_z-K_v)=b+p_v-p_z.$$

오른쪽 값이 홀수이면 모순이다. 그렇지 않으면 두 등식을 각각 서로 반대 방향의 두 차분 제약으로 추가할 수 있다.

$u$에서 $z$에 도착하기 전의 정점 $x$에서는 $z$보다 먼저 배터리가 $0$이 되면 안 되므로 $H_x<H_z$여야 한다. 따라서

$$K_x-K_z\le \begin{cases} -1 & p_z=0,\\ 0 & p_z=1,\ p_x=0,\\ -1 & p_z=1,\ p_x=1. \end{cases}$$

이다.

$z$를 지난 뒤의 정점 $x$에서는 $H_x\le H_z$이면 된다. 따라서

$$K_x-K_z\le \begin{cases} 0 & p_z=0,\ p_x=0,\\ -1 & p_z=0,\ p_x=1,\\ 0 & p_z=1. \end{cases}$$

이다.

보조 변수 $X_0$을 두고 $K_v=X_v-X_0$으로 해석한다. 은 , 은 과 으로 표현한다. 이제 모든 조건은

$$X_y-X_x\le c$$

꼴의 차분 제약이다.

문제는 기록 하나가 경로 위의 많은 정점에 제약을 만든다는 점이다. 이를 정점마다 직접 추가하면 제약 수가 $O(NM)$이 된다. Bellman-Ford까지 그대로 수행하면 충분히 빠르지 않다.

Bellman-Ford를 동기식으로 생각하자. 현재 거리를 $D$, 다음 라운드의 거리를 $D'$라 하면, 처음에 $D'=D$로 둔 뒤 모든 제약 $x\to$에 대해

$$D'_y\leftarrow\min(D'_y,D_x+c)$$

를 수행한다. 실제 변수는 $0,1,\cdots,N$뿐이므로 총 $N+1$번의 라운드만 확인하면 된다.

기록에서 생기는 경로 제약은 모두 어떤 정점 $z$에서 경로 위 정점들로 향한다. 가중치는 도착 정점의 깊이 짝홀에만 의존한다. 따라서 하나의 경로 제약을 두 값 $(C_0,C_1)$로 나타낼 수 있다. 깊이가 짝수인 정점 $x$에는 , 홀수인 정점에는 을 후보로 준다.

한 라운드에서 이러한 경로 relax를 HLD로 한꺼번에 처리한다.

HLD의 한 체인에 속한 정점들은 체인의 머리부터 아래쪽 순서로 연속하게 놓인다. 일반적인 트리 경로를 HLD로 분해하면 $O(\log N)$개의 완전한 체인 prefix

$$[\operatorname{head}(x),x]$$

와 마지막 한 체인 안의 구간 하나로 나타낼 수 있다.

완전한 체인 prefix에는 세그먼트 트리 갱신을 하지 않는다. 그 prefix의 끝점 $x$에 $(C_0,C_1)$을 저장한다. 모든 기록을 처리한 뒤 각 체인을 아래에서 위로 한 번 훑으면서 지금까지 본 값의 최솟값을 유지하면, 모든 prefix 갱신을 $O(N)$에 각 정점으로 전파할 수 있다. prefix 갱신 하나의 비용은 이다.

마지막 한 체인 안의 일반 구간만 lazy 세그먼트 트리에 range chmin을 한다. 각 세그먼트 트리 노드에도 깊이 짝홀용 두 최솟값을 저장한다. 갱신 하나는 $O(\log N)$이고, 모든 갱신이 끝난 뒤 태그를 리프까지 한 번 전파하면 $O(N)$에 모든 정점의 후보를 얻는다.

따라서 트리 경로 하나의 relax는 HLD에서 체인을 건너는 횟수 $O(\log N)$과 마지막 구간 갱신 $O(\log N)$을 합쳐 $O(\log N)$에 처리된다. 한 기록에서 필요한 경로는 $z$ 이전과 이후 두 개뿐이다. 를 제외한 각 경로의 끝점은 LCA와 binary lifting으로 미리 구할 수 있다.

한 Bellman-Ford 라운드의 비용은 다음과 같다.

• 간선 조건, 비음수 조건, 기록의 등식 조건: $O(N+M)$.
• 기록의 경로 조건: $O(M\log N)$.
• HLD prefix와 세그먼트 트리 태그를 실제 정점으로 전파: $O(N)$.

따라서 전체 시간 복잡도는

$$O\left(N(N+M\log N)\right)$$

이고, binary lifting을 포함한 메모리 복잡도는 $O(N\log N+M)$이다.

초기 거리를 모두 $0$으로 두면 모든 변수로 가중치 $0$의 간선을 갖는 슈퍼 소스를 둔 것과 같다. $N+1$번째 라운드에서도 값이 감소한다면 음수 사이클이 존재하므로 답은 없다. 그 전에 더 이상 감소하지 않으면 최종 거리 $D$에 대해

$$K_v=D_v-D_0,\qquad H_v=2K_v+p_v$$

로 높이를 복원한다.

증명

배터리가 $C+H_u-H_x$라는 식에서, 이동 중 배터리가 음수가 되지 않기 위한 최소 $C$는 경로 최대 높이와 의 차이다. 이 최소 배터리로 배터리가 인 정점은 정확히 경로 최대 높이를 갖는 정점이다. 따라서 기록은 에서의 두 높이 차 등식, 이전의 엄격한 상한, 이후의 일반 상한과 정확히 동치이다.

Solution written by GPT5.6