各交差点に対して、その交差点から距離 \(R\) 以下にあるお店が \(1\) 軒であるような日時は区間となります。したがって、各頂点に対して距離 \(R\) 以下にあるお店がちょうど \(1\) 軒となった時刻・ちょうど \(1\) 軒でなくなった時刻が求められれば imos 法を用いることでこの問題を解くことができます。

以降交差点・道路を木と見なし、単に頂点・辺と呼びます。

\(i=1,2,\ldots,Q\) に対し、頂点 \(C_i\) に \(i\) を書き込みます。

ここで、\(d[x][r]\) を「頂点 \(x\) から距離 \(r\) 以下の頂点に書き込まれた数の最小値・\(2\) 番目に小さい値」とします。求めたい値は \(x=1,2,\ldots,N\) に対する \(d[x][R]\) です。

まず \(d[x][0]\) はその頂点に書き込まれた値が最小値、\(2\) 番目に小さい値は \(\infty\) です。また、\(d[x][r+1]\) から \(d[x][r]\) への遷移は各辺に対して更新を行うことで求めることができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(NR)\) です。

実装例(Python3)

input = __import__("sys").stdin.readline
n, q, r = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
d1 = [q] * n
d2 = [q] * n
for i in range(q):
    c = int(input())
    c -= 1
    d1[c] = i
for _ in range(r):
    dd1 = d1[:]
    dd2 = d2[:]

    def add(idx, x):
        if x < dd1[idx]:
            dd2[idx] = dd1[idx]
            dd1[idx] = x
            return
        if dd1[idx] < x < dd2[idx]:
            dd2[idx] = x

    for st in range(n):
        for v in g[st]:
            add(v, d1[st])
            add(v, d2[st])
    d1 = dd1
    d2 = dd2
ans = [0] * (q + 1)
for i in range(n):
    ans[d1[i]] += 1
    ans[d2[i]] -= 1
for i in range(q):
    ans[i + 1] += ans[i]
print("\n".join(map(str, ans[:q])))