## Editorial for DMOPC '20 Contest 7 P4 - Mimi and Carrots II

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

For the first subtask, we can answer each query with a brute force DFS in .

**Time Complexity:**

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 pathWe 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 pathWe 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 cityA 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.

**Time Complexity:**

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

## Comments