概要

木上の各町に消防署があり、開設中の消防署集合が動的に変化します。
各問い合わせでは、町 \(V\) から最も近い開設中の消防署までの距離が \(T\) 以下かを判定します。

考察

この問題は、次のように言い換えられます。

• 木上に「有効な頂点集合」がある
• 頂点の追加・削除が発生する
• ある頂点 \(V\) から、有効な頂点集合までの最短距離を求めたい

町 \(1\) の消防署は常に開設されているので、有効な頂点集合は常に空になりません。

素朴な方法

各タイプ 2 の問い合わせで、現在開設中の消防署すべてについて距離を計算し、その最小値を取る方法を考えます。

2 頂点間距離は LCA を使えば \(O(\log N)\) で求められますが、開設中の消防署が最大で \(N\) 個あるため、1 回の問い合わせに \(O(N \log N)\) かかります。

\(N, Q \leq 5 \times 10^4\) なので、最悪で \(O(NQ \log N)\) となり間に合いません。

必要な工夫

動的に変化する頂点集合に対して、

• 頂点の追加
• 頂点の削除
• ある頂点から集合内の最近点を求める

を高速に処理したいです。

このような「木上の最近点クエリ」には 重心分解 が有効です。

アルゴリズム

1. 木上の距離を求める準備

まず、元の木を町 \(1\) を根として根付き木にします。

各頂点 \(v\) について、

• depth[v]: 根からの深さ
• rootDist[v]: 根から \(v\) までの距離
• up[k][v]: \(v\) の \(2^k\) 個上の祖先

を前計算します。

すると、2 頂点 \(a, b\) の距離は LCA を使って

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

で求められます。

このコードでは LCA を二分累乗法で求めているため、距離計算は \(O(\log N)\) です。

---

2. 重心分解

重心分解では、木から「重心」を選び、その重心を取り除いてできる部分木に対して再帰的に同じ処理を行います。

重心とは、その頂点を取り除いたときにできる各成分のサイズが、元の木のサイズの半分以下になるような頂点です。

重心分解によって作られる木を「重心分解木」と考えると、任意の頂点から重心分解木の根までの高さは \(O(\log N)\) になります。

コード中では、

cdParent[v]

に、重心分解木における頂点 \(v\) の親を持たせています。

---

3. 各重心に対して距離情報を持つ

各重心 \(c\) について、

ms[c]

という multiset を用意します。

ms[c] には、現在開設中の消防署 \(x\) のうち、重心分解木で \(c\) が \(x\) の祖先になっているものについて、

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

を入れておきます。

つまり、消防署 \(x\) を開設するときは、重心分解木上で

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

と根までたどり、それぞれの重心 \(c\) に対して

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

を ms[c] に追加します。

削除するときも同様に、各 ms[c] から対応する距離を 1 つ削除します。

multiset を使う理由は、同じ距離の消防署が複数存在する可能性があるためです。

---

4. 問い合わせの処理

町 \(v\) で火災が起きたとします。

重心分解木上で、\(v\) から根までの重心 \(c\) をすべて見ると、候補距離は

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

です。

ここで \(\min_x \operatorname{dist}(x, c)\) は ms[c] の最小値、つまり *ms[c].begin() で得られます。

したがって、答えは

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

です。

コードでは次のように計算しています。

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. なぜこれで正しいか

任意の開設中の消防署 \(x\) と問い合わせ頂点 \(v\) を考えます。

重心分解木上で、\(x\) と \(v\) の最も近い共通祖先を \(c\) とします。

重心分解の性質より、元の木における \(x\) から \(v\) へのパスは、この重心 \(c\) を通ります。

したがって、

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

が成り立ちます。

また、\(c\) は \(v\) の重心分解木上の祖先なので、問い合わせ時に必ず調べられます。
さらに、\(c\) は \(x\) の祖先でもあるので、消防署 \(x\) を開設したときに \(\operatorname{dist}(x,c)\) が ms[c] に入っています。

そのため、最近の消防署への距離は、問い合わせで調べる候補の中に必ず含まれます。

よって、この方法で正しく最短距離を求められます。

計算量

• 時間計算量: \(O(N \log N + Q \log^2 N)\)
• 空間計算量: \(O(N \log N)\)

LCA の前計算と重心分解に \(O(N \log N)\) かかります。

各イベントでは、重心分解木の高さが \(O(\log N)\) なので、調べる重心は \(O(\log N)\) 個です。
各距離計算に LCA を使って \(O(\log N)\) かかるため、1 イベントあたり \(O(\log^2 N)\) です。

実装のポイント

• 辺の重みや距離は最大で大きくなるため、long long を使います。

• 町 \(1\) の消防署は最初から開設しているので、イベント処理の前に add_station(1) を呼びます。

• タイプ 1 のイベントでは町 \(1\) は与えられないため、町 \(1\) が閉鎖されることはありません。

• multiset から削除するときは、同じ値が複数ある可能性があるので、erase(value) ではなく find して得たイテレータを 1 つだけ削除します。

• 重心分解の深さは \(O(\log N)\) なので、cdParent をたどる処理は高速に行えます。

  ソースコード

#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;
}

---

この解説は gpt-5.5-xhigh によって生成されました。