概要

木構造上で消防署の開設/閉鎖を動的に切り替えながら、任意の町から最も近い開設中の消防署までの距離が閾値以下かを判定する問題。重心分解（Centroid Decomposition） を用いて効率的に最近傍クエリを処理する。

考察

素朴なアプローチの問題点

各クエリで全ての開設中消防署との距離を計算すると、最悪 \(O(NQ)\) となり \(N, Q \leq 5 \times 10^4\) では間に合わない可能性がある（定数倍次第だが、木上の距離計算にLCAなどが必要で重い）。

重要な気づき

木の上での「動的な点集合に対する最近傍クエリ」は、重心分解 を使うと効率的に解ける。

重心分解の鍵となる性質：木上の任意の2頂点 \(u, v\) のパスは、重心分解木における \(u\) と \(v\) の最小共通祖先（のうちの一つ）を必ず通る。したがって、各重心 \(c\) に対して「\(c\) の管轄内にある開設中消防署から \(c\) までの距離」を管理しておけば、クエリ頂点 \(v\) の全祖先を見るだけで最近傍距離が求まる。

アルゴリズム

1. 重心分解の構築

木を再帰的に重心分解する。各頂点 \(v\) について、重心分解木における全祖先（自分自身を含む）とその距離を ancestors[v] に記録する。

2. データ構造の管理

各重心 \(c\) に対して multiset<long long> ms[c] を持つ。これは、\(c\) の管轄範囲内にある「開設中の消防署」から \(c\) までの距離の集合。

3. Toggle 操作（1 X）

町 \(X\) の消防署を切り替える際、ancestors[X] に格納された全ての祖先 \((c, d)\) に対して： - 開設時：ms[c] に距離 \(d\) を挿入 - 閉鎖時：ms[c] から距離 \(d\) を1つ削除

4. Query 操作（2 V T）

町 \(V\) から最寄りの消防署までの距離を求める。ancestors[V] の全祖先 \((c, d_v)\) に対して、\(d_v + \min(ms[c])\) を計算し、全体の最小値を取る。

なぜこれで正しいか： 開設中の消防署 \(u\) と頂点 \(V\) の経路は、重心分解木上で共通の祖先 \(c\) を必ず持つ。そのとき \(dist(u, V) = dist(u, c) + dist(c, V)\) が成り立つ（\(c\) は実際の木上のパスの途中にある重心）。

具体例

    1
   / \
  2   3
     / \
    4   5

重心が 3 だとすると、町 4 の ancestors は [(4, 0), (3, cost(3→4)), (重心分解の上位, ...)] のようになる。町 4 でクエリが来たら、各祖先について multiset の最小値と自分の距離を足し合わせて最小を取る。

計算量

• 前処理（重心分解）: \(O(N \log N)\)
• Toggle 操作: 祖先の数は \(O(\log N)\) 個、multiset の操作は \(O(\log N)\) → 1回あたり \(O(\log^2 N)\)
• Query 操作: 祖先 \(O(\log N)\) 個を走査、multiset の最小値取得は \(O(1)\) → 1回あたり \(O(\log N)\)
• 時間計算量: \(O(N \log N + Q \log^2 N)\)
• 空間計算量: \(O(N \log N)\)（各頂点の祖先リストと multiset の合計サイズ）

実装のポイント

• 距離は long long で管理する：辺の重みが最大 \(10^9\)、パスの長さが最大 \(N\) なので距離は最大 \(5 \times 10^{13}\) 程度になりうる。

• removed フラグ：重心分解の構築時、すでに重心として選ばれた頂点を除外するために使用。

• 初期状態の処理：町 1 は最初から開設されているので、構築後に明示的に toggle（または直接挿入）する。

• multiset の erase：ms[c].erase(ms[c].find(d)) で1つだけ削除する。erase(d) だと同じ値が全て消えてしまうので注意。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。