Overview

A problem where fire stations are dynamically opened/closed on a tree structure, and we need to determine whether the distance from any given town to the nearest open fire station is within a threshold. We use Centroid Decomposition to efficiently handle nearest-neighbor queries.

Analysis

Problems with the Naive Approach

If we compute the distance to all open fire stations for each query, the worst case is \(O(NQ)\), which may not be fast enough for \(N, Q \leq 5 \times 10^4\) (depending on constant factors, since computing distances on a tree requires LCA or similar heavy operations).

Key Insight

“Dynamic nearest-neighbor queries over a point set on a tree” can be efficiently solved using Centroid Decomposition.

The key property of centroid decomposition: the path between any two vertices \(u, v\) on the tree always passes through (one of) the lowest common ancestors of \(u\) and \(v\) in the centroid decomposition tree. Therefore, if we maintain for each centroid \(c\) the “distances from open fire stations within \(c\)’s jurisdiction to \(c\)”, we can find the nearest-neighbor distance by simply examining all ancestors of the query vertex \(v\).

Algorithm

1. Building the Centroid Decomposition

Recursively perform centroid decomposition on the tree. For each vertex \(v\), record all ancestors in the centroid decomposition tree (including itself) along with their distances in ancestors[v].

2. Data Structure Management

For each centroid \(c\), maintain a multiset<long long> ms[c]. This stores the set of distances from “open fire stations” within \(c\)’s jurisdiction to \(c\).

3. Toggle Operation (1 X)

When toggling the fire station at town \(X\), for all ancestors \((c, d)\) stored in ancestors[X]: - On opening: insert distance \(d\) into ms[c] - On closing: remove one instance of distance \(d\) from ms[c]

4. Query Operation (2 V T)

Find the distance from town \(V\) to the nearest fire station. For all ancestors \((c, d_v)\) in ancestors[V], compute \(d_v + \min(ms[c])\), and take the overall minimum.

Why this is correct: The path between an open fire station \(u\) and vertex \(V\) always shares a common ancestor \(c\) in the centroid decomposition tree. At that point, \(dist(u, V) = dist(u, c) + dist(c, V)\) holds (\(c\) is a centroid that lies on the actual path in the tree).

Concrete Example

    1
   / \
  2   3
     / \
    4   5

If the centroid is 3, then the ancestors of town 4 would be something like [(4, 0), (3, cost(3→4)), (higher centroid, ...)]. When a query arrives for town 4, we add the minimum value in each ancestor’s multiset to our own distance and take the minimum.

Complexity

• Preprocessing (Centroid Decomposition): \(O(N \log N)\)
• Toggle Operation: Number of ancestors is \(O(\log N)\), multiset operations are \(O(\log N)\) → \(O(\log^2 N)\) per operation
• Query Operation: Traverse \(O(\log N)\) ancestors, obtaining the minimum of a multiset is \(O(1)\) → \(O(\log N)\) per operation
• Time Complexity: \(O(N \log N + Q \log^2 N)\)
• Space Complexity: \(O(N \log N)\) (total size of ancestor lists and multisets for all vertices)

Implementation Notes

• Manage distances with long long: Edge weights can be up to \(10^9\) and path lengths up to \(N\), so distances can reach approximately \(5 \times 10^{13}\).

• removed flag: Used during centroid decomposition construction to exclude vertices already chosen as centroids.

• Initial state handling: Town 1 is open from the start, so after construction, explicitly toggle it (or directly insert).

• erase on multiset: Use ms[c].erase(ms[c].find(d)) to delete only one instance. Using erase(d) would remove all instances with the same value, so be careful.

  Source Code

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

const int MAXN = 50005;
vector<pair<int, long long>> adj[MAXN];
int sz[MAXN];
bool removed[MAXN];
vector<pair<int, long long>> ancestors[MAXN];
multiset<long long> ms[MAXN];
bool is_open[MAXN];
int n, q;

int get_subtree_size(int v, int p) {
    sz[v] = 1;
    for (auto [u, w] : adj[v])
        if (u != p && !removed[u])
            sz[v] += get_subtree_size(u, v);
    return sz[v];
}

int get_centroid(int v, int p, int tree_size) {
    for (auto [u, w] : adj[v])
        if (u != p && !removed[u] && sz[u] > tree_size / 2)
            return get_centroid(u, v, tree_size);
    return v;
}

void get_distances(int v, int p, int centroid, long long dist) {
    ancestors[v].push_back({centroid, dist});
    for (auto [u, w] : adj[v])
        if (u != p && !removed[u])
            get_distances(u, v, centroid, dist + w);
}

void build(int v) {
    int tree_size = get_subtree_size(v, -1);
    int centroid = get_centroid(v, -1, tree_size);
    removed[centroid] = true;
    get_distances(centroid, -1, centroid, 0);
    for (auto [u, w] : adj[centroid])
        if (!removed[u])
            build(u);
}

void toggle(int x) {
    is_open[x] = !is_open[x];
    for (auto [c, d] : ancestors[x]) {
        if (is_open[x])
            ms[c].insert(d);
        else
            ms[c].erase(ms[c].find(d));
    }
}

long long query(int v) {
    long long res = LLONG_MAX;
    for (auto [c, d] : ancestors[v])
        if (!ms[c].empty())
            res = min(res, d + *ms[c].begin());
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    build(1);
    
    is_open[1] = true;
    for (auto [c, d] : ancestors[1])
        ms[c].insert(d);
    
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            toggle(x);
        } else {
            int v;
            long long t;
            cin >> v >> t;
            long long min_dist = query(v);
            cout << (min_dist <= t ? "YES" : "NO") << "\n";
        }
    }
    
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.