How will the town change after a journey from a to b that travels through r roads? If it’s not snowing, the roads between a to b are simply set to zero snow. If it is snowing, the roads from a to b are set to r, …, 3, 2, 1 cm of snow, and every other road gains additional r cm of snow.
Updating every road during every journey would be too slow. Instead, let’s keep a global timer. For every road, we remember the last time we visited it, and we only advance the timer when we clean a road while it’s snowing. The amount of snow on a road is simply the current time minus the last visited time. This way, we only need to update the roads we actually visit.
In the easy subproblem, we now effectively have an array of roads, and we need to quickly find the sum of a range, or update a range to contain an arithmetic progression, such that the difference between consecutive terms being either 0 if it’s not snowing, or -1 or 1 if it’s snowing depending on the travel direction. This can be done with a lazy-propagation segment tree, modified so that instead of simply setting a range to a constant value, we lazily remember the arithmetic progression that belongs to the current node and propagate the correct half to each child.
To extend this to the hard subproblem, we can use heavy path decomposition to split the initial tree into a set of disjoint paths such that going from any a to any b only intersects O(logn) of those paths. Then we build a segment tree for each heavy path, allowing us to process a journey in O(log2n).