For the first subtask, we can answer each query with a brute force DFS in ~\mathcal O(N)~.

Time Complexity: ~\mathcal O(QN)~

For the second subtask, we can use square root decomposition. We partition the nodes into those with outdegree less than or equal to ~\sqrt N~ and those with outdegree greater than ~\sqrt N~. 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 ~n~, and subtract ~1~ from ~n~. Similarly, if a light node is changed from a safe to an unsafe city, then we subtract 1 from all neighbours of ~n~, and add ~1~ to ~n~.

When querying for the number of safe cities from ~A~ to ~B~, we consider 5 cases:

1. 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.

2. 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. ~1 + 1 - 1 = 1~, thus the node will be counted exactly once.

3. ~A~ or ~B~ is a light node, and is a safe city

   A simple path query will give us ~1 - 1 = 0~, thus we must check both endpoints and add them to the total.

We can then iterate the ~\sqrt N~ 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 ~\operatorname{LCA}(A, B)~ is a heavy safe city.

We can perform the updates in ~\mathcal O(1)~ and queries in ~\mathcal O(\sqrt N)~ using square root decomposition over the Euler tour.

Time Complexity: ~\mathcal O(Q \sqrt N)~

Alternatively, define ~f(v) = 1~ if it is safe, and 0 otherwise. Let ~g(u)~ be the sum of ~f(v)~ over all children ~v~ of ~u~.
Then the sum in question is the sum of ~g(v)~ over all ~v~ on the path between ~a~ and ~b~, plus ~f(l)~ and ~f(p)~, where ~l = \mathrm{LCA}(a,b)~ and ~p~ is the parent of ~l~.

This can be solved using HLD or similar techniques.

Time Complexity: ~\mathcal O(Q \log^2 N)~ or ~\mathcal O(Q \log N)~