Solution for USACO 2026 First Contest, Silver, P2

Preface

这是一篇英文题解。This is an English solution.

Solution

Build an undirected graph with the given $m$ constraints, connecting vertices $x$ and $y$ with an edge weighted $z$. After that, consider every connected component independently.

Case 1: The connected component has at least $|V|$ edges, i.e. it’s not a tree.

In this case, there is a fixed solution if and only if there is an odd cycle in the graph. Conversely, every even cycle has a redundant edge. For example:

$\begin{cases} a + b = k_1\\b+c=k_2\\c+d=k_3\\ \color{gray}a+d=k_4 \end{cases}$

where $a+d=k_4$ is redundant, since we could know the value of $a+d$ is $k_1+k_3-k_2$ with the previous 3 equations. Specifically, when we detect an even cycle, we have to check if the weight on the redundant edge doesn’t contradict other edges on the cycle (check if $k_4=k_1+k_3-k_2$ in the example).

If no contradiction in an even cycle is detected and the graph doesn’t have an odd cycle, remove the redundant edges and treat it as a tree (Case 2). Otherwise, the solution for every vertex is fixed. We could simply calculate one value of $a_i$ on a vertex in an odd cycle, then let that vertex be the root of a spanning tree of the graph, and we could calculate the rest values via the spanning tree. Make sure the constraints of the edges which aren’t on the spanning tree are satisfied, then check whether $l_i\leq a_i\leq r_i$ is true for each vertex.

For implementation, it’s convenient to find a DFS-tree of the graph first to detect all odd and even cycles.

Case 2: The connected component has $|V|-1$ edges, i.e. it’s a tree.

In this case, there isn’t a fixed solution for the set of equations. Let the root of the tree be $rt$. We’re able to generate a solution set for the tree after we determine the value of $a_{rt}$. Assume we’ve already known that $a_{rt}=c$, and let $w_u=W-w_{fa_u}$, where $fa_u$ is the parent of vertex $u$ on the tree and $W$ is the weight of the edge connecting $fa_u$ and $u$. It’s easy to verify that, $l_u\leq a_u\leq r_u$ is satisfied if and only if:

• $w_u-r_u\leq c\leq w_u-l_u$, if the depth of $u$ is an odd number.
• $l_u-w_u\leq c\leq r_u-w_u$, if the depth of $u$ is an even number.

We define the depth $d$ of vertex $u$ as $d_{fa_u}+1$, and the depth of $rt$ is $0$.

Now, our goal becomes choosing a value of $c$ that is covered by the maximum number of segments. This problem could be solved by simply increasing the values at all positions within the range by $1$ for each segment using a difference array, and then finding the position with the maximum value as the result. We need to discretize the values of the endpoints of the segments before processing.

The time complexity of the solution is $\mathcal{O}(n\log n+m)$, since we have to sort the elements in Case 2.