交差点と道路のなすグラフを \(G\) とします。

計算量を考慮しない場合、新しいお店がオープンするたびにその頂点から深さ優先探索（DFS）を行えば解けますが、グラフの形状によっては1回の探索に \(\Theta(N)\) の時間がかかります。

(入力省略)
cnt = [0] * N
ans = 0

def dfs(x, p, d):
  cnt[x] += 1
  if cnt[x] == 1: ans += 1
  if cnt[x] == 2: ans -= 1
  if d == 0: return
  for y in G[x]:
    if y == p: continue
    dfs(y, p, d - 1)

for c in C:
  dfs(c, -1, R)
  print(ans)

ある状態 \((x, d)\)（頂点 \(x\) に残り距離 \(d\) で到達）での呼び出しがすでに \(k\) 回以上行われている場合、そこから再帰的に到達可能な頂点もすべてすでに \(k\) 回以上探索済みとなります。

本問題において求めるのは「距離 \(R\) 以内にあるお店の数がちょうど \(1\) 軒」の交差点の数であり、各頂点におけるお店の数が「\(1\) 軒」か「\(2\) 軒以上」かのみを区別できれば十分です。そのため、ある頂点の訪問回数が \(3\) 回以上になっても答えには影響しません。

したがって、状態 \((x, d)\) ごとに呼び出された回数を管理し、\(3\) 回目以降の呼び出し時は再帰を打ち切るように枝刈りを行うことで高速化できます。状態数が \(O(NR)\) であるため全体の計算量は \(O(Q+NR)\) 時間となります。