概要

木構造のグラフにおいて、動的に変化する「開設された消防署」の集合に対し、指定された町から最も近い消防署への距離を求める問題です。消防署の切り替え（更新）と最短距離の判定（クエリ）を効率的に処理するため、重心分解（Centroid Decomposition）を活用します。

考察

1. 素朴なアプローチとその限界

各クエリに対して、現在開設されているすべての消防署から町 \(V\) への距離を計算する場合、最悪で \(O(N)\) の時間がかかります。クエリ数が \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、制約の \(N, Q \leq 5 \times 10^4\) では間に合いません（約 \(2.5 \times 10^9\) 回の計算が必要）。

2. 木における距離の性質と重心分解

木上の 2 点 \(u, v\) 間の距離 \(\text{dist}(u, v)\) を考える際、ある特定のノード \(c\) を経由する経路に注目すると、もし \(c\) が \(u\) と \(v\) を結ぶパス上にあれば \(\text{dist}(u, v) = \text{dist}(u, c) + \text{dist}(c, v)\) が成り立ちます。

重心分解を行うと、任意の 2 点 \(u, v\) に対して、それらを結ぶパス上に必ず「\(u\) と \(v\) の共通の重心祖先」が存在することが保証されます。これを利用して、各町 \(V\) について「自分を部分木に含むすべての重心祖先 \(c\)」を経由した最短距離を管理することで、全域を探索せずに最短距離を求めることができます。

アルゴリズム

1. 重心分解の事前準備

1. 木を重心分解し、各ノード \(u\) に対して以下の情報を記録します。
   • 自身を配下に持つ重心祖先 \(c\) のリスト
   • 各重心祖先までの距離 \(\text{dist}(u, c)\)
2. 各重心 \(c\) ごとに、その配下にある「現在開設されている消防署」から \(c\) までの距離を格納する最小ヒープ（優先度付きキュー）を用意します。

重心分解の性質上、各ノードが持つ重心祖先の数は高々 \(O(\log N)\) 個です。

2. イベントの処理

• タイプ 1（消防署の状態切り替え）:
  • 町 \(X\) の消防署を開設する場合：\(X\) のすべての重心祖先 \(c\) に対して、ヒープに \(\text{dist}(X, c)\) を追加します。
  • 閉鎖する場合：ヒープから \(\text{dist}(X, c)\) を削除します。
  • ※ 標準的なヒープは任意要素の削除が苦手なため、削除予定の値を管理する別のヒープを併用する「Lazy Deletion（遅延削除）」などの手法を用います。
• タイプ 2（最短距離の照会）:
  • 町 \(V\) からの最短距離は、すべての重心祖先 \(c\) についての \(\min(\text{dist}(V, c) + [c \text{ のヒープの最小値}])\) で求められます。
  • この値が \(T\) 以下であれば YES、そうでなければ NO を出力します。

計算量

• 事前準備（重心分解）: \(O(N \log N)\)

• タイプ 1（更新）: 重心祖先の数 \(O(\log N)\) × ヒープ操作 \(O(\log N) = O(\log^2 N)\)

• タイプ 2（クエリ）: 重心祖先の数 \(O(\log N)\) × ヒープの参照 \(O(1)\)（または \(O(\log N)\)）\(= O(\log N)\) または \(O(\log^2 N)\)

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

  • \(N, Q = 5 \times 10^4\) の場合、\(\log_2 N \approx 16\) なので、十分実行時間制限内に収まります。

• 空間計算量: \(O(N \log N)\)

  • 各ノードが \(O(\log N)\) 個の重心祖先情報を保持するためです。

実装のポイント

• 削除可能ヒープ: std::priority_queue を 2 つ使い、一方に挿入された要素、もう一方に削除された要素を入れることで、実質的に任意要素の削除が可能なヒープ（RemovableHeap）を構築すると実装がスムーズです。

• 重心分解の再帰: 重心を見つける get_centroid と、サイズを計算する get_size を適切に実装します。一度重心として選んだノードは removed フラグを立てて、以降の探索から除外します。

• 初期状態: 町 1 は最初から開設されているため、あらかじめタイプ 1 の「開設」処理を行っておく必要があります。

  ソースコード

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

---

この解説は gemini-3-flash-thinking によって生成されました。