概要

各交差点について、距離 \(R\) 以内にあるお店の「最も早い開店日」と「2 番目に早い開店日」を求めます。
その交差点が嬉しいのは、最初のお店が開店してから、2 番目のお店が開店する直前までです。

考察

ある交差点 \(x\) に注目します。

距離 \(R\) 以下にあるお店の開店日を小さい順に

\[ d_1 < d_2 < d_3 < \cdots \]

とします。

このとき、\(i\) 日目の終わりに距離 \(R\) 以下のお店がちょうど \(1\) 軒であるのは、

\[ d_1 \leq i < d_2 \]

のときです。

例えば、距離 \(R\) 以内のお店の開店日が \(3, 7, 10\) 日目なら、

• \(1, 2\) 日目：お店は \(0\) 軒
• \(3, 4, 5, 6\) 日目：お店は \(1\) 軒
• \(7\) 日目以降：お店は \(2\) 軒以上

なので、この交差点は \(3\) 日目から \(6\) 日目まで答えに \(1\) 貢献します。

つまり、各交差点について必要なのは、距離 \(R\) 以内にあるお店の開店日のうち、

• 最小値
• 2 番目に小さい値

だけです。

---

素朴に、各日ごとに新しく開店したお店から距離 \(R\) 以内の交差点を探索して更新すると、1 回の探索で最大 \(O(N)\) 個の交差点を見る可能性があります。
例えば星型の木では、\(R = 1\) でも中心から全頂点に届きます。

そのため、全体で \(O(NQ)\) となり、制約では間に合いません。

ここでは全ての開店予定を先に読み込み、各交差点から見て「近くのお店の開店日の最小 2 つ」をまとめて求めるオフライン解法を使います。

\(R \leq 20\) と小さいため、距離を \(1\) ずつ広げるようにして、木全体で伝播させます。

アルゴリズム

各交差点 \(v\) について、次の 2 つの値を持ちます。

• a[v]：距離 \(k\) 以下にあるお店の開店日の最小値
• b[v]：距離 \(k\) 以下にあるお店の開店日の 2 番目に小さい値

最初は距離 \(0\) の情報だけを持っています。

• 交差点 \(v\) にお店が開くなら、a[v] = 開店日
• そうでなければ、a[v] = INF
• b[v] = INF

とします。

その後、これを \(R\) 回繰り返します。

1 回の操作で、各辺 \(u - v\) について、

• \(v\) が知っている情報を \(u\) に伝える
• \(u\) が知っている情報を \(v\) に伝える

ことで、距離を \(1\) だけ広げます。

ただし、同じ回の中で更新した情報をさらに使ってしまうと、1 回で距離 \(2\) 以上伝播してしまいます。
そのため、各回では必ず古い配列 a, b から読み、新しい配列 na, nb に書き込みます。

---

この処理を \(R\) 回行うと、各交差点 \(v\) について、

• a[v]：距離 \(R\) 以下にあるお店の最も早い開店日
• b[v]：距離 \(R\) 以下にあるお店の 2 番目に早い開店日

が求まります。

あとは各交差点ごとに答えへの貢献期間を考えます。

• a[v] = x
• b[v] = y

とします。

もし \(x\) が存在しない、つまり INF なら、その交差点の距離 \(R\) 以内にはお店が一度も開かないので、何も足しません。

そうでなければ、その交差点が嬉しい日は

\[ x \leq \text{day} < y \]

です。

もし \(y\) が存在しないなら、\(x\) 日目から \(Q\) 日目までずっと嬉しいです。

このような区間加算を全交差点について行うため、差分配列を使います。

• \(x\) 日目から加算開始：diff[x] += 1
• \(y\) 日目で加算終了：diff[y] -= 1
• 2 番目のお店がない場合は、diff[Q + 1] -= 1

最後に差分配列の累積和を取れば、各日の答えが得られます。

計算量

• 時間計算量: \(O(RN + Q)\)
• 空間計算量: \(O(N + Q)\)

\(R \leq 20\) なので、十分高速です。

実装のポイント

2 つの最小値を管理するときは、同じ開店日を重複して数えないようにします。

伝播の途中では、同じお店の情報が複数回候補として現れることがあります。
そのため、値を追加するときは、

• 最小値より小さければ更新
• 最小値とは異なり、2 番目より小さければ更新

という形にします。

また、各距離の伝播では必ずコピーを作り、

na = a[:]
nb = b[:]

として、新しい情報を書き込むようにします。
これにより、1 回のループで距離が余分に広がることを防げます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0
    N = data[idx]
    Q = data[idx + 1]
    R = data[idx + 2]
    idx += 3

    M = N - 1
    us = [0] * M
    vs = [0] * M
    for i in range(M):
        u = data[idx] - 1
        v = data[idx + 1] - 1
        idx += 2
        us[i] = u
        vs[i] = v

    INF = 10 ** 9
    a = [INF] * N
    b = [INF] * N

    for day in range(1, Q + 1):
        c = data[idx] - 1
        idx += 1
        a[c] = day

    for _ in range(R):
        na = a[:]
        nb = b[:]
        oa = a
        ob = b

        for u, v in zip(us, vs):
            av = oa[v]
            bv = ob[v]
            m1 = na[u]
            m2 = nb[u]

            if av < m1:
                m2 = m1
                m1 = av
            elif av != m1 and av < m2:
                m2 = av

            if bv < m1:
                m2 = m1
                m1 = bv
            elif bv != m1 and bv < m2:
                m2 = bv

            na[u] = m1
            nb[u] = m2

            au = oa[u]
            bu = ob[u]
            m1 = na[v]
            m2 = nb[v]

            if au < m1:
                m2 = m1
                m1 = au
            elif au != m1 and au < m2:
                m2 = au

            if bu < m1:
                m2 = m1
                m1 = bu
            elif bu != m1 and bu < m2:
                m2 = bu

            na[v] = m1
            nb[v] = m2

        a = na
        b = nb

    diff = [0] * (Q + 2)

    for x, y in zip(a, b):
        if x <= Q:
            diff[x] += 1
            if y <= Q:
                diff[y] -= 1
            else:
                diff[Q + 1] -= 1

    ans = []
    cur = 0
    for day in range(1, Q + 1):
        cur += diff[day]
        ans.append(str(cur))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。