Editorial for An Animal Contest 1 P5 - Odd Alpacas
Submitting an official solution before solving the problem yourself is a bannable offence.
We first observe that only the parity of an edge is relevant. Thus, the only relevant change we can make to a road is to change the parity of its length.
For the first subtask, we perform a graph search from each node , storing the results in a distance array and tallying the number of odd and even pathways. We repeat this step after changing the parity of each edge and track the minimum absolute difference.
Let us denote to be the distance from the root village to .
The distance between any two nodes and in a tree can be formulated as where is the lowest common ancestor of and .
Since is even, it does not affect the parity of the result, and the result is completely determined by the parity of and .
So, we perform a single DFS from an arbitrary root. To determine the number of odd pathways, we multiply the number of villages with an even distance by the number of villages with an odd distance. Complementary counting can be used to determine the number of even pathways.
We repeat this step after changing the parity of each edge and track the minimum absolute difference.
Let us define an "odd" node as an arbitrary village such that .
Similarly, an "even" node is an arbitrary village such that .
The number of "odd" and "even" nodes is used in the previous subtask to calculate the number of odd and even pathways in time. Given the circumstances of subtask 3, for each modification, we must recalculate the number of odd and even pathways in constant time.
Suppose edge is to be modified (i.e. change its parity). Denote to be the node with lower depth among and . Then, it is easy to see that only the nodes in the subtree of will be affected by the edge modification. This is because for any path to intersect , either node or node must be in the subtree of .
Given this fact, all odd nodes in the subtree will become even nodes and vice versa. All that is left to do is keep track of the number of odd and even nodes in the subtree of each node , which can be computed recursively within the DFS function.