Overview

For each intersection, we find the earliest opening shop and the second earliest opening shop among “shops within distance \(R\).”
Once we have this information, we can represent the “happy” period for each intersection as an interval, and use a difference array to compute the answer for each day.

Analysis

Let us focus on a particular intersection \(x\).

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

\[ t_1, t_2, t_3, \dots \]

Then, the number of open shops within distance \(R\) at the end of day \(i\) is the count of \(t_j \leq i\).

Therefore, intersection \(x\) is happy during the period:

• From the day the first shop opens, \(t_1\), onward
• Before the day the second shop opens, \(t_2\)

In other words, the happy days are

\[ t_1 \leq i < t_2 \]

If there is only one shop within distance \(R\), then it is happy from day \(t_1\) through the last day \(Q\).

Thus, for each intersection, we only need two things:

• The minimum opening day among shops within distance \(R\)
• The second smallest opening day among shops within distance \(R\)

For example, suppose the shops within distance \(R\) from some intersection open on days 3, 7, and 10.
This intersection is happy from day 3 to day 6.

This can be represented using a difference array as:

• diff[3] += 1
• diff[7] -= 1

If we naively check all intersections within distance \(R\) from each newly opened shop on each day, a single search could take \(O(N)\) in cases like a star-shaped tree.
Doing this for \(Q\) days results in \(O(NQ)\), which is too slow for the given constraints.

Instead, we look at all opening days in advance and compute the “smallest two opening days within distance \(R\)” for each intersection all at once.

The key observation here is that \(R \leq 20\), which is small.
By propagating the “smallest two opening days” through edges \(R\) times, we can obtain information for all shops within distance \(R\).

Algorithm

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

• best1[v]: The earliest opening day known so far
• best2[v]: The second earliest opening day known so far

Initially, we consider only distance \(0\), i.e., the intersection itself.

• If a shop opens at intersection \(C_i\), set best1[C_i] = i
• For intersections where no shop opens, set the value to INF

Next, we repeat the following \(R\) times.

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

• Propagate the smallest two opening days known by \(v\) to \(u\)
• Propagate the smallest two opening days known by \(u\) to \(v\)

As a result, after the 1st iteration the information covers distance \(\leq 1\), after the 2nd iteration distance \(\leq 2\), and so on.
After \(R\) iterations, we obtain the smallest two opening days among shops within distance \(R\) for each intersection.

When adding candidates, we must avoid counting the same opening day more than once,
since information about the same shop may arrive via multiple paths.
In this problem, exactly one shop opens per day, so the opening day uniquely identifies a shop.

Finally, for each intersection \(x\), let:

• first = best1[x]
• second = best2[x]

If first does not exist (i.e., there are no shops within distance \(R\)), this intersection does not affect the answer.

If first exists:

• diff[first] += 1
• If second exists, diff[second] -= 1

Then, by computing the prefix sum of the difference array, we obtain the answer for each day.

Complexity

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

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

Implementation Details

When updating best1[v] and best2[v], we need to maintain the “smallest two distinct values.”

For example, a function that adds a new candidate t works as follows:

• If t is INF, ignore it
• If t is already equal to best1 or best2, ignore it
• If t < best1, set best2 = best1 and best1 = t
• Otherwise, if t < best2, set best2 = t

Also, during the propagation step, to prevent updates within the same step from cascading further, we create a next array nxt from the current array and then swap them.
This guarantees that each iteration extends the distance by exactly 1.

Source Code

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

inline void add_candidate(int &a, int &b, int t) {
    if (t == INF) return;
    if (t == a || t == b) return;

    if (t < a) {
        b = a;
        a = t;
    } else if (t < b) {
        b = t;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q, R;
    cin >> N >> Q >> R;

    vector<pair<int, int>> edges;
    edges.reserve(max(0, N - 1));

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        edges.emplace_back(u, v);
    }

    vector<int> best1(N, INF), best2(N, INF);

    for (int i = 1; i <= Q; i++) {
        int c;
        cin >> c;
        --c;
        best1[c] = i;
    }

    for (int step = 0; step < R; step++) {
        vector<int> nxt1 = best1;
        vector<int> nxt2 = best2;

        for (auto [u, v] : edges) {
            add_candidate(nxt1[u], nxt2[u], best1[v]);
            add_candidate(nxt1[u], nxt2[u], best2[v]);

            add_candidate(nxt1[v], nxt2[v], best1[u]);
            add_candidate(nxt1[v], nxt2[v], best2[u]);
        }

        best1.swap(nxt1);
        best2.swap(nxt2);
    }

    vector<long long> diff(Q + 3, 0);

    for (int x = 0; x < N; x++) {
        int first = best1[x];
        int second = best2[x];

        if (first <= Q) {
            diff[first]++;
            if (second <= Q) diff[second]--;
        }
    }

    long long ans = 0;
    for (int i = 1; i <= Q; i++) {
        ans += diff[i];
        cout << ans << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.