Editorial for DMOPC '20 Contest 7 P4 - Mimi and Carrots II
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, we can answer each query with a brute force DFS in .
For the second subtask, we can use square root decomposition. We partition the nodes into those with outdegree less than or equal to and those with outdegree greater than . Let us call the first group of nodes light nodes, and the second group heavy nodes.
Let us start by rooting the tree arbitrarily.
If a light node is changed from an unsafe city to a safe city, then we can add 1 to all neighbours of , and subtract from . Similarly, if a light node is changed from a safe to an unsafe city, then we subtract 1 from all neighbours of , and add to .
When querying for the number of safe cities from to , we consider 5 cases:
A light node not on the path is a safe city and has a neighbour on the path
We added 1 to all neighbours of this node, thus it will be counted exactly once.
A light node on the path is a safe city and has a neighbour on the path
We added 1 to all neighbours of this node, and subtracted one from the value of the node. , thus the node will be counted exactly once.
or is a light node, and is a safe city
A simple path query will give us , thus we must check both endpoints and add them to the total.
We can then iterate the heavy nodes, and check if they are either on the path, or if their parent is on the path. The final edge case involves checking if the parent of is a heavy safe city.
We can perform the updates in and queries in using square root decomposition over the Euler tour.
Alternatively, define if it is safe, and 0 otherwise. Let be the sum of over all children of .
Then the sum in question is the sum of over all on the path between and , plus and , where and is the parent of .
This can be solved using HLD or similar techniques.
Time Complexity: or