Overview

Each town on a tree has a fire station, and the set of open fire stations changes dynamically.
For each query, we determine whether the distance from town \(V\) to the nearest open fire station is at most \(T\).

Analysis

This problem can be rephrased as follows:

• There is a “set of active vertices” on a tree
• Vertices are added to or removed from this set
• We want to find the shortest distance from a given vertex \(V\) to the set of active vertices

Since the fire station at town \(1\) is always open, the set of active vertices is never empty.

Naive Approach

For each type 2 query, we consider computing the distance to all currently open fire stations and taking the minimum.

The distance between two vertices can be computed in \(O(\log N)\) using LCA, but since there can be up to \(N\) open fire stations, a single query takes \(O(N \log N)\).

Since \(N, Q \leq 5 \times 10^4\), the worst case is \(O(NQ \log N)\), which is too slow.

Required Optimization

For a dynamically changing vertex set, we want to efficiently handle:

• Adding a vertex
• Removing a vertex
• Finding the nearest point in the set from a given vertex

For such “nearest point queries on a tree,” centroid decomposition is effective.

Algorithm

1. Preparation for Computing Distances on the Tree

First, we root the original tree at town \(1\).

For each vertex \(v\), we precompute:

• depth[v]: depth from the root
• rootDist[v]: distance from the root to \(v\)
• up[k][v]: the \(2^k\)-th ancestor of \(v\)

Then, the distance between two vertices \(a, b\) can be computed using LCA as:

\[ \operatorname{dist}(a, b) = \operatorname{rootDist}[a] + \operatorname{rootDist}[b] - 2 \times \operatorname{rootDist}[\operatorname{LCA}(a,b)] \]

In this code, LCA is computed using binary lifting, so distance computation is \(O(\log N)\).

---

2. Centroid Decomposition

In centroid decomposition, we select a “centroid” from the tree, remove it, and recursively perform the same process on the resulting subtrees.

A centroid is a vertex such that when it is removed, each resulting component has size at most half of the original tree’s size.

If we think of the tree constructed by centroid decomposition as the “centroid decomposition tree,” the height from any vertex to the root of the centroid decomposition tree is \(O(\log N)\).

In the code,

cdParent[v]

stores the parent of vertex \(v\) in the centroid decomposition tree.

---

3. Maintaining Distance Information for Each Centroid

For each centroid \(c\), we prepare a multiset:

ms[c]

ms[c] stores, for each currently open fire station \(x\) such that \(c\) is an ancestor of \(x\) in the centroid decomposition tree, the value:

\[ \operatorname{dist}(x, c) \]

That is, when opening fire station \(x\), we traverse up the centroid decomposition tree:

\[ x \rightarrow cdParent[x] \rightarrow cdParent[cdParent[x]] \rightarrow \cdots \]

up to the root, and for each centroid \(c\) along the way, we add

\[ \operatorname{dist}(x, c) \]

to ms[c].

When closing a station, we similarly remove one corresponding distance from each ms[c].

The reason for using a multiset is that multiple fire stations may have the same distance.

---

4. Processing Queries

Suppose a fire occurs at town \(v\).

Looking at all centroids \(c\) from \(v\) to the root in the centroid decomposition tree, the candidate distance is:

\[ \operatorname{dist}(v, c) + \min_{x} \operatorname{dist}(x, c) \]

Here, \(\min_x \operatorname{dist}(x, c)\) is the minimum value in ms[c], which is obtained by *ms[c].begin().

Therefore, the answer is:

\[ \min_c \left( \operatorname{dist}(v, c) + \min ms[c] \right) \]

In the code, this is computed as follows:

ll ans = INF;

for (int c = v; c != 0; c = cdParent[c]) {
    if (!ms[c].empty()) {
        ans = min(ans, dist(v, c) + *ms[c].begin());
    }
}

---

5. Why This is Correct

Consider any open fire station \(x\) and query vertex \(v\).

Let \(c\) be the lowest common ancestor of \(x\) and \(v\) in the centroid decomposition tree.

By the properties of centroid decomposition, the path from \(x\) to \(v\) in the original tree passes through this centroid \(c\).

Therefore,

\[ \operatorname{dist}(x, v) = \operatorname{dist}(x, c) + \operatorname{dist}(c, v) \]

holds.

Also, since \(c\) is an ancestor of \(v\) in the centroid decomposition tree, it is always examined during the query.
Furthermore, since \(c\) is also an ancestor of \(x\), \(\operatorname{dist}(x,c)\) was added to ms[c] when fire station \(x\) was opened.

Therefore, the distance to the nearest fire station is always included among the candidates examined during the query.

Thus, this method correctly computes the shortest distance.

Complexity

• Time complexity: \(O(N \log N + Q \log^2 N)\)
• Space complexity: \(O(N \log N)\)

The LCA precomputation and centroid decomposition take \(O(N \log N)\).

For each event, since the height of the centroid decomposition tree is \(O(\log N)\), we examine \(O(\log N)\) centroids.
Each distance computation using LCA takes \(O(\log N)\), so each event costs \(O(\log^2 N)\).

Implementation Notes

• Since edge weights and distances can become large, use long long.

• Since the fire station at town \(1\) is open from the start, call add_station(1) before processing events.

• In type 1 events, town \(1\) is never given, so the fire station at town \(1\) is never closed.

• When deleting from a multiset, since there may be multiple entries with the same value, do not use erase(value). Instead, use find to get an iterator and erase only one element.

• Since the depth of the centroid decomposition is \(O(\log N)\), traversing cdParent is performed efficiently.

  Source Code

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

using ll = long long;
const ll INF = (1LL << 62);

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

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

    vector<vector<pair<int, ll>>> g(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    int LOG = 1;
    while ((1 << LOG) <= N) LOG++;

    vector<vector<int>> up(LOG, vector<int>(N + 1, 1));
    vector<int> depth(N + 1, 0);
    vector<ll> rootDist(N + 1, 0);

    {
        vector<int> parent(N + 1, 0);
        stack<int> st;
        st.push(1);
        parent[1] = 1;
        up[0][1] = 1;

        while (!st.empty()) {
            int v = st.top();
            st.pop();

            for (auto [to, cost] : g[v]) {
                if (to == parent[v]) continue;
                parent[to] = v;
                up[0][to] = v;
                depth[to] = depth[v] + 1;
                rootDist[to] = rootDist[v] + cost;
                st.push(to);
            }
        }

        for (int k = 1; k < LOG; k++) {
            for (int v = 1; v <= N; v++) {
                up[k][v] = up[k - 1][up[k - 1][v]];
            }
        }
    }

    auto lca = [&](int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);

        int diff = depth[a] - depth[b];
        for (int k = 0; k < LOG; k++) {
            if (diff & (1 << k)) a = up[k][a];
        }

        if (a == b) return a;

        for (int k = LOG - 1; k >= 0; k--) {
            if (up[k][a] != up[k][b]) {
                a = up[k][a];
                b = up[k][b];
            }
        }

        return up[0][a];
    };

    auto dist = [&](int a, int b) -> ll {
        int c = lca(a, b);
        return rootDist[a] + rootDist[b] - 2LL * rootDist[c];
    };

    vector<int> cdParent(N + 1, 0);
    vector<int> sub(N + 1, 0);
    vector<int> tmpParent(N + 1, 0);
    vector<char> removed(N + 1, false);

    auto get_centroid = [&](int start) {
        vector<int> nodes;
        nodes.reserve(N);

        stack<int> st;
        st.push(start);
        tmpParent[start] = 0;

        while (!st.empty()) {
            int v = st.top();
            st.pop();
            nodes.push_back(v);

            for (auto [to, cost] : g[v]) {
                if (removed[to] || to == tmpParent[v]) continue;
                tmpParent[to] = v;
                st.push(to);
            }
        }

        for (int v : nodes) sub[v] = 1;

        for (int i = (int)nodes.size() - 1; i >= 0; i--) {
            int v = nodes[i];
            if (tmpParent[v] != 0) sub[tmpParent[v]] += sub[v];
        }

        int total = (int)nodes.size();
        int centroid = start;
        int best = total + 1;

        for (int v : nodes) {
            int mx = total - sub[v];

            for (auto [to, cost] : g[v]) {
                if (removed[to]) continue;
                if (tmpParent[to] == v) {
                    mx = max(mx, sub[to]);
                }
            }

            if (mx < best) {
                best = mx;
                centroid = v;
            }
        }

        return centroid;
    };

    function<void(int, int)> build_cd = [&](int start, int par) {
        int c = get_centroid(start);
        cdParent[c] = par;
        removed[c] = true;

        for (auto [to, cost] : g[c]) {
            if (!removed[to]) {
                build_cd(to, c);
            }
        }
    };

    build_cd(1, 0);

    vector<multiset<ll>> ms(N + 1);
    vector<char> active(N + 1, false);

    auto add_station = [&](int x) {
        for (int c = x; c != 0; c = cdParent[c]) {
            ms[c].insert(dist(x, c));
        }
    };

    auto remove_station = [&](int x) {
        for (int c = x; c != 0; c = cdParent[c]) {
            ll d = dist(x, c);
            auto it = ms[c].find(d);
            if (it != ms[c].end()) ms[c].erase(it);
        }
    };

    auto nearest = [&](int v) {
        ll ans = INF;

        for (int c = v; c != 0; c = cdParent[c]) {
            if (!ms[c].empty()) {
                ans = min(ans, dist(v, c) + *ms[c].begin());
            }
        }

        return ans;
    };

    active[1] = true;
    add_station(1);

    for (int qi = 0; qi < Q; qi++) {
        int type;
        cin >> type;

        if (type == 1) {
            int x;
            cin >> x;

            if (active[x]) {
                remove_station(x);
                active[x] = false;
            } else {
                add_station(x);
                active[x] = true;
            }
        } else {
            int v;
            ll t;
            cin >> v >> t;

            cout << (nearest(v) <= t ? "YES" : "NO") << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.