Overview

For each intersection, we find the “earliest opening day” and “second earliest opening day” among shops within distance \(R\).
An intersection is happy from the day the first shop opens until just before the second shop opens.

Analysis

Let’s focus on a particular intersection \(x\).

Let the opening days of shops within distance \(R\) or less be, in increasing order:

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

Then, at the end of day \(i\), there is exactly \(1\) shop within distance \(R\) or less when:

\[ d_1 \leq i < d_2 \]

For example, if the opening days of shops within distance \(R\) are days \(3, 7, 10\), then:

• Days \(1, 2\): there are \(0\) shops
• Days \(3, 4, 5, 6\): there is \(1\) shop
• Day \(7\) onwards: there are \(2\) or more shops

So this intersection contributes \(1\) to the answer from day \(3\) through day \(6\).

In other words, for each intersection, all we need are the following among the opening days of shops within distance \(R\):

• The minimum value
• The second smallest value

---

Naively, if we search for intersections within distance \(R\) from each newly opened shop on each day and update them, a single search may visit up to \(O(N)\) intersections.
For example, in a star-shaped tree, even with \(R = 1\), the center can reach all vertices.

Therefore, the overall complexity becomes \(O(NQ)\), which is too slow for the constraints.

Here, we use an offline approach where we read all opening schedules in advance and compute the “smallest 2 opening days among nearby shops” for each intersection collectively.

Since \(R \leq 20\) is small, we expand the distance by \(1\) at a time, propagating across the entire tree.

Algorithm

For each intersection \(v\), we maintain the following two values:

• a[v]: the minimum opening day among shops within distance \(k\) or less
• b[v]: the second smallest opening day among shops within distance \(k\) or less

Initially, we only have information for distance \(0\).

• If a shop opens at intersection \(v\): a[v] = opening day
• Otherwise: a[v] = INF
• b[v] = INF

After that, we repeat the following \(R\) times.

In one operation, for each edge \(u - v\):

• Propagate the information \(v\) knows to \(u\)
• Propagate the information \(u\) knows to \(v\)

This extends the distance by \(1\).

However, if we use information updated within the same round, it could propagate distance \(2\) or more in a single round.
Therefore, in each round, we always read from the old arrays a, b and write to new arrays na, nb.

---

After performing this process \(R\) times, for each intersection \(v\):

• a[v]: the earliest opening day among shops within distance \(R\) or less
• b[v]: the second earliest opening day among shops within distance \(R\) or less

are obtained.

Then, we consider the contribution period to the answer for each intersection.

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

If \(x\) does not exist, i.e., it is INF, then no shop ever opens within distance \(R\) of that intersection, so we add nothing.

Otherwise, the days when that intersection is happy are:

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

If \(y\) does not exist, then it is happy from day \(x\) through day \(Q\).

To perform such range additions for all intersections, we use a difference array.

• Start adding from day \(x\): diff[x] += 1
• Stop adding at day \(y\): diff[y] -= 1
• If there is no second shop: diff[Q + 1] -= 1

Finally, taking the prefix sum of the difference array gives the answer for each day.

Complexity

• Time complexity: \(O(RN + Q)\)
• Space complexity: \(O(N + Q)\)

Since \(R \leq 20\), this is sufficiently fast.

Implementation Notes

When managing the two smallest values, be careful not to count the same opening day as a duplicate.

During propagation, information from the same shop may appear multiple times as a candidate.
Therefore, when adding a value:

• If it is smaller than the minimum, update
• If it is different from the minimum and smaller than the second smallest, update

Also, for each distance propagation step, always make a copy:

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

and write new information to these copies.
This prevents the distance from expanding more than intended in a single loop iteration.

Source Code

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()

---

This editorial was generated by gpt-5.5-high.