Overview

In a town with a tree structure consisting of \(N\) intersections, a new shop opens every day. At the end of each day, we need to find how many intersections have exactly 1 shop within distance \(R\).

Analysis

1. Focus on the constraint of \(R\)

The most important hint in this problem is that the distance limit \(R\) is at most 20, which is very small. If \(R\) were large, advanced data structures for paths and distances on trees (such as centroid decomposition or Heavy-Light Decomposition) would be necessary. However, since \(R \le 20\), an approach that directly propagates information within distance \(R\) from each vertex is effective.

2. Organize the “happy” condition

An intersection \(x\) is considered “happy” on a given day when the following conditions are met: - The earliest-opening shop among all shops within distance \(R\) has already opened. - The second earliest-opening shop among all shops within distance \(R\) has not yet opened.

Each shop is assigned an opening day (day \(1\) through day \(Q\)). Let \(B1_x\) be the minimum and \(B2_x\) be the second minimum among the opening days of shops within distance \(R\) from intersection \(x\). Then, the period during which intersection \(x\) is happy is from day \(B1_x\) to day \(B2_x - 1\). (If there are no shops or only one shop, we consider \(B2_x = \infty\).)

3. How to compute \(B1_x, B2_x\)

Using a dynamic programming (DP)-like approach, we can spread information by incrementing the distance by \(1\) at a time. - When \(dist=0\): For each intersection \(u\), store the shop number (day) that opens at that location into \(B1_u\). - When \(dist=k\): Use the results from distance \(k-1\) to update the results for distance \(k\). Specifically, update \(B1, B2\) of vertex \(u\) using the \(B1, B2\) values at distance \(k-1\) from all adjacent vertices \(v\).

By repeating this \(R\) times, we can efficiently compute the “minimum opening day” and “second minimum opening day” among shops within distance \(R\) from each vertex.

Algorithm

1. Initialization:

   • For each intersection \(u\), record the day \(i\) on which a shop opens at that intersection. If no shop opens there, set it to infinity (\(\infty\)).
   • This serves as the “minimum value \(B1_u\) at distance \(0\).”

2. Information Propagation (DP):

   • Repeat the following for distance \(d = 1\) to \(R\).
   • For each vertex \(u\), gather the “minimum and second minimum at distance \(d-1\)” from itself and all adjacent vertices \(v\), select the two smallest values among them, and update \(B1_u, B2_u\) of vertex \(u\) for “distance \(d\).”

3. Aggregation (Difference Array / Imos Method):

   • For each intersection \(u\), the happy period \([B1_u, B2_u - 1]\) is known.
   • To record this period for all intersections, prepare a difference array (imos method) of length \(Q+2\).
   • Perform the operations diff[B1_u]++ and diff[B2_u]--.

4. Output:

   • By taking the prefix sum of the difference array, output the total number of “happy intersections” for each day \(i\).

Complexity

• Time Complexity: \(O(R \times (N + M) + Q)\)
  • The information propagation scans all edges (\(M = N-1\)) for \(R\) iterations, resulting in \(O(RN)\).
  • The final aggregation takes \(O(N + Q)\).
  • Since \(R \le 20\), this runs sufficiently fast.
• Space Complexity: \(O(N + Q)\)
  • We need an adjacency list and arrays to store \(B1, B2\) for each vertex.

Implementation Notes

• Updating the two minimum values: Create a function update(b1, b2, x) that, if x is smaller than the current minimum b1, slides the values as b2 = b1, b1 = x, and if x is larger than b1 but smaller than b2, updates b2 = x.

• Swapping values: Since all updates at each step \(d\) must be performed simultaneously, you need to manage separate arrays for reading the current values and writing the next step’s values (or use swap).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// INF is set to a value larger than any possible shop index (Q <= 2e5)
const int INF = 1e9;

/**
 * Updates the smallest (b1) and second smallest (b2) values with a new value (x).
 * Ensures that b1 and b2 remain distinct and represent the minimums of the set.
 */
inline void update(int& b1, int& b2, int x) {
    if (x >= b2) return;
    if (x < b1) {
        b2 = b1;
        b1 = x;
    } else if (x > b1) {
        b2 = x;
    }
}

int main() {
    // Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q, R;
    if (!(cin >> N >> Q >> R)) return 0;

    // Build the tree as an adjacency list
    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // B1[u] and B2[u] store the smallest and second smallest shop indices within distance d from node u.
    // Initially, d = 0, so B1[u] is the index of the shop at u if it exists.
    vector<int> B1(N + 1, INF), B2(N + 1, INF);
    for (int i = 1; i <= Q; ++i) {
        int c;
        cin >> c;
        B1[c] = i;
    }

    // Dynamic Programming to calculate B1 and B2 for distance up to R.
    // In each step d, we update the minimums for distance d using values from distance d-1.
    vector<int> nextB1(N + 1), nextB2(N + 1);
    for (int d = 0; d < R; ++d) {
        for (int u = 1; u <= N; ++u) {
            nextB1[u] = B1[u];
            nextB2[u] = B2[u];
        }
        for (int u = 1; u <= N; ++u) {
            for (int v : adj[u]) {
                // Neighbors' shops at distance d-1 are at distance d from current node u.
                update(nextB1[u], nextB2[u], B1[v]);
                update(nextB1[u], nextB2[u], B2[v]);
            }
        }
        B1.swap(nextB1);
        B2.swap(nextB2);
    }

    // After R steps, B1[u] and B2[u] represent the two smallest indices of shops within distance R of u.
    // Node u is "happy" on day i if exactly one shop within distance R is open.
    // This happens if the first shop (index B1[u]) is open (B1[u] <= i) 
    // and the second shop (index B2[u]) is NOT yet open (B2[u] > i).
    
    // We use a difference array to count happy nodes for each day efficiently.
    vector<int> diff(Q + 2, 0);
    for (int u = 1; u <= N; ++u) {
        if (B1[u] <= Q) {
            diff[B1[u]]++;
            if (B2[u] <= Q) {
                diff[B2[u]]--;
            }
        }
    }

    // Prefix sum of the difference array gives the answer for each day.
    int current_happy_count = 0;
    for (int i = 1; i <= Q; ++i) {
        current_happy_count += diff[i];
        cout << current_happy_count << "\n";
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.