Exploration Records

Root the tree at vertex $1$. Let $d_v$ be the depth of vertex $v$, and let $p_v=d_v\bmod 2$.

If the robot starts at $u$ with battery level $C$ and reaches a vertex $x$ on the path, its battery level is

$$C+H_u-H_x.$$

Therefore, if $H_{\max}$ is the maximum height on the path from $u$ to $v$,

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

and $Z(u,v)$ is the first vertex of height $H_{\max}$ when the path is traversed from $u$ to $v$.

Every edge changes the height by exactly $1$, and $H_1=0$. Hence

$$H_v\equiv d_v\pmod 2.$$

Define the integer variable

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

Then $H_v=2K_v+p_v$ and .

For an edge whose parent is $q$ and whose child is $c$, the edge condition is equivalent to

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

Consider a record $(u,v,a,b,z)$. First, $z$ must lie on the path from $u$ to $v$.

Since $H_z-H_u=a$ and $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.$$

If either right-hand side is odd, the record is impossible. Otherwise, each equality is represented by two opposite difference constraints.

For a vertex $x$ strictly before $z$ on the path, the battery must not have reached $0$ yet, so $H_x<H_z$. Therefore

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

For a vertex $x$ after $z$, it is sufficient to have $H_x\le H_z$. Thus

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

Introduce an auxiliary variable $X_0$ and interpret $K_v=X_v-X_0$. The condition becomes , and becomes both and . Every condition is now a difference constraint

$$X_y-X_x\le c.$$

The difficulty is that one record creates constraints to many vertices on a path. Expanding every such constraint explicitly produces $O(NM)$ edges, which is too slow when combined with Bellman-Ford.

Use synchronous Bellman-Ford. Let $D$ be the distances before one round and $D'$ the distances after the round. Start with $D'=D$, and for every constraint edge $$ perform

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

There are only the variables $0,1,\cdots,N$, so it is enough to examine $N+1$ rounds.

Every path constraint created by a record goes from one vertex $z$ to vertices on a tree path. Its weight depends only on the depth parity of the destination. Hence one path constraint can be represented by a pair $(C_0,C_1)$: an even-depth vertex $x$ receives candidate , and an odd-depth vertex receives .

Process all such relaxations in one Bellman-Ford round with HLD.

Vertices of one HLD chain are stored consecutively from the chain head downward. The usual HLD decomposition of an arbitrary tree path consists of $O(\log N)$ complete chain prefixes

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

and one final interval contained in a single chain.

For a complete chain prefix, do not perform a segment-tree update. Store the pair $(C_0,C_1)$ only at its lower endpoint $x$. After all records have been processed, scan each chain once from bottom to top while maintaining the minimum pair seen so far. This propagates every prefix update to exactly the vertices it covers. Each prefix update costs $O($, and all prefix propagation costs .

Only the final interval inside one chain is processed by a lazy segment tree with a range-chmin update. Every segment-tree node stores two minimum tags, one for each depth parity. One update costs $O(\log N)$. After all updates, pushing the tags to all leaves costs $O(N)$.

Thus one tree-path relaxation costs $O(\log N)$: there are $O(\log N)$ chain changes with $O(1)$ prefix updates, plus one $O(\log N)$ interval update. Each record needs only two such paths, one before and one after . Their endpoints excluding can be precomputed with LCA and binary lifting.

The cost of one Bellman-Ford round is:

• edge constraints, nonnegativity constraints, and equality constraints from records: $O(N+M)$;
• path constraints from records: $O(M\log N)$;
• propagation of HLD-prefix and segment-tree tags to actual vertices: $O(N)$.

Therefore, the total time complexity is

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

and the memory complexity, including binary lifting, is $O(N\log N+M)$.

Initialize every distance to $0$, which is equivalent to adding a super source with a zero-weight edge to every variable. If a value still decreases in the $(N+1)$-st round, a negative cycle exists and no answer is possible. Otherwise, once the distances stabilize, recover

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

Proof

From the expression $C+H_u-H_x$ for the battery level, the minimum valid initial battery is exactly the path maximum minus $H_u$. With that minimum battery, the battery is exactly at vertices attaining the path maximum. Hence a record is equivalent to the two height-difference equalities at , the strict upper bounds before , and the non-strict upper bounds after .

Solution written by GPT5.6