Overview

In a tree-structured graph, given a dynamically changing set of “opened fire stations,” the problem asks to find the distance from a specified town to the nearest fire station. To efficiently handle toggling fire stations (updates) and determining shortest distances (queries), we utilize Centroid Decomposition.

Analysis

1. Naive Approach and Its Limitations

For each query, computing the distance from town \(V\) to all currently opened fire stations takes \(O(N)\) time in the worst case. With \(Q\) queries, the total complexity becomes \(O(NQ)\), which is too slow for the constraints \(N, Q \leq 5 \times 10^4\) (requiring approximately \(2.5 \times 10^9\) computations).

2. Distance Properties in Trees and Centroid Decomposition

When considering the distance \(\text{dist}(u, v)\) between two points \(u, v\) on a tree, if we focus on a path passing through a specific node \(c\), and if \(c\) lies on the path connecting \(u\) and \(v\), then \(\text{dist}(u, v) = \text{dist}(u, c) + \text{dist}(c, v)\) holds.

By performing centroid decomposition, for any two points \(u, v\), it is guaranteed that there exists a “common centroid ancestor of \(u\) and \(v\)” on the path connecting them. Using this property, for each town \(V\), we can manage the shortest distance via “all centroid ancestors \(c\) that contain \(V\) in their subtree,” allowing us to find the shortest distance without searching the entire tree.

Algorithm

1. Preprocessing with Centroid Decomposition

1. Perform centroid decomposition on the tree and record the following information for each node \(u\):
   • The list of centroid ancestors \(c\) that have \(u\) in their subtree
   • The distance \(\text{dist}(u, c)\) to each centroid ancestor
2. For each centroid \(c\), prepare a min-heap (priority queue) that stores the distances from currently opened fire stations in its subtree to \(c\).

Due to the properties of centroid decomposition, the number of centroid ancestors each node has is at most \(O(\log N)\).

2. Event Processing

• Type 1 (Toggle fire station state):
  • When opening a fire station at town \(X\): For all centroid ancestors \(c\) of \(X\), add \(\text{dist}(X, c)\) to the heap.
  • When closing: Remove \(\text{dist}(X, c)\) from the heap.
  • Note: Since standard heaps do not efficiently support arbitrary element deletion, techniques such as “Lazy Deletion” using a separate heap to manage values scheduled for deletion are employed.
• Type 2 (Shortest distance query):
  • The shortest distance from town \(V\) is computed as \(\min(\text{dist}(V, c) + [\text{minimum value in } c\text{'s heap}])\) over all centroid ancestors \(c\).
  • If this value is at most \(T\), output YES; otherwise, output NO.

Complexity

• Preprocessing (Centroid Decomposition): \(O(N \log N)\)

• Type 1 (Update): Number of centroid ancestors \(O(\log N)\) × heap operation \(O(\log N) = O(\log^2 N)\)

• Type 2 (Query): Number of centroid ancestors \(O(\log N)\) × heap access \(O(1)\) (or \(O(\log N)\)) \(= O(\log N)\) or \(O(\log^2 N)\)

• Overall: \(O(N \log N + Q \log^2 N)\)

  • For \(N, Q = 5 \times 10^4\), since \(\log_2 N \approx 16\), this comfortably fits within the time limit.

• Space Complexity: \(O(N \log N)\)

  • This is because each node maintains \(O(\log N)\) centroid ancestor information.

Implementation Notes

• Removable Heap: By using two std::priority_queue instances—one storing inserted elements and another storing deleted elements—you can construct a heap (RemovableHeap) that effectively supports arbitrary element deletion, making the implementation smooth.

• Centroid Decomposition Recursion: Properly implement get_centroid to find the centroid and get_size to compute subtree sizes. Once a node is selected as a centroid, set a removed flag to exclude it from subsequent searches.

• Initial State: Since town 1 is opened from the beginning, the Type 1 “open” operation must be performed for it in advance.

  Source Code

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

using namespace std;

/**
 * The problem asks for the minimum distance from a given town V to any town in a dynamic set of "open" fire stations.
 * Since the towns and roads form a tree, we can use Centroid Decomposition to solve this efficiently.
 * For each node, we maintain its centroid ancestors and the distance to each.
 * For each centroid, we maintain a collection of distances from all currently open fire stations that have this centroid as an ancestor.
 * A min-priority queue with lazy deletion can be used to efficiently find the minimum distance for each centroid.
 */

struct Edge {
    int to;
    long long cost;
};

struct Ancestor {
    int id;
    long long dist;
};

// A priority queue that supports deletion of specific elements
struct RemovableHeap {
    priority_queue<long long, vector<long long>, greater<long long>> pq, del;

    void push(long long x) {
        pq.push(x);
    }

    void erase(long long x) {
        del.push(x);
    }

    void normalize() {
        while (!del.empty() && !pq.empty() && pq.top() == del.top()) {
            pq.pop();
            del.pop();
        }
    }

    long long top() {
        normalize();
        return pq.top();
    }

    bool empty() {
        normalize();
        return pq.empty();
    }
};

const int MAXN = 50005;
vector<Edge> adj[MAXN];
vector<Ancestor> ancestors[MAXN];
int sz[MAXN];
bool removed[MAXN];
RemovableHeap min_dists[MAXN];
bool is_open[MAXN];

// Standard subtree size calculation for centroid decomposition
int get_size(int u, int p) {
    sz[u] = 1;
    for (auto& edge : adj[u]) {
        if (edge.to != p && !removed[edge.to]) {
            sz[u] += get_size(edge.to, u);
        }
    }
    return sz[u];
}

// Standard centroid finding for centroid decomposition
int get_centroid(int u, int p, int total_size) {
    for (auto& edge : adj[u]) {
        if (edge.to != p && !removed[edge.to]) {
            if (sz[edge.to] > total_size / 2) {
                return get_centroid(edge.to, u, total_size);
            }
        }
    }
    return u;
}

// DFS to collect distances to the current centroid for all nodes in its component
void dfs_collect_ancestors(int u, int p, long long d, int centroid) {
    ancestors[u].push_back({centroid, d});
    for (auto& edge : adj[u]) {
        if (edge.to != p && !removed[edge.to]) {
            dfs_collect_ancestors(edge.to, u, d + edge.cost, centroid);
        }
    }
}

// Recursive centroid decomposition
void decompose(int u) {
    int total_size = get_size(u, -1);
    int c = get_centroid(u, -1, total_size);
    removed[c] = true;
    dfs_collect_ancestors(c, -1, 0, c);
    for (auto& edge : adj[c]) {
        if (!removed[edge.to]) {
            decompose(edge.to);
        }
    }
}

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

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

    // Read road information
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    // Perform centroid decomposition
    decompose(1);

    // Initial state: only town 1 has an open fire station
    is_open[1] = true;
    for (auto& anc : ancestors[1]) {
        min_dists[anc.id].push(anc.dist);
    }

    // Process Q events
    for (int i = 0; i < Q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            // Type 1: Toggle fire station at town X
            int X;
            cin >> X;
            if (is_open[X]) {
                // If open, close it: remove distances from centroid heaps
                for (auto& anc : ancestors[X]) {
                    min_dists[anc.id].erase(anc.dist);
                }
                is_open[X] = false;
            } else {
                // If closed, open it: add distances to centroid heaps
                for (auto& anc : ancestors[X]) {
                    min_dists[anc.id].push(anc.dist);
                }
                is_open[X] = true;
            }
        } else {
            // Type 2: Query minimum distance from town V to any open fire station
            int V;
            long long T;
            cin >> V >> T;
            long long min_d = -1;
            // Iterate through centroid ancestors to find the global minimum distance
            for (auto& anc : ancestors[V]) {
                if (!min_dists[anc.id].empty()) {
                    long long d = anc.dist + min_dists[anc.id].top();
                    if (min_d == -1 || d < min_d) {
                        min_d = d;
                    }
                }
            }
            // Check if the minimum distance is within the threshold T
            if (min_d != -1 && min_d <= T) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}

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