概要

木構造のネットワーク上で、各中継局の動作モード切り替えや補正パラメータの更新を行いながら、指定された2点間のパスに沿った通信コストを計算するシミュレーション問題です。

考察

• 木構造において、任意の2頂点 \(A\), \(B\) 間のパスは一意に定まります。そのパスを見つけて通信コストを計算すればよいです。
• 制約が \(N \leq 5000\), \(Q \leq 5000\) と比較的小さいため、クエリごとにパスを求め直しても十分間に合います。
• 各中継局の実効座標は動作モードによって \((X_i, Y_i)\) または \((-X_i, -Y_i)\) になるため、クエリ時点でのモードを参照して計算する必要があります。
• 高度なデータ構造（Heavy-Light Decomposition など）は不要で、愚直にBFSでパスを求めて辺ごとにコストを足し上げるアプローチで十分です。

アルゴリズム

1. 入力の読み込みと初期化: 各中継局の座標、木の辺情報を読み込む。全中継局を通常モード、\(S = 0\) で初期化する。

2. 操作1 (1 C): 中継局 \(C\) の動作モードのフラグを反転する。

3. 操作2 (2 W): \(S\) に \(W\) を加算する。

4. 操作3 (3 A B): 以下の手順で答えを計算する。

   • \(A = B\) の場合、パス上の中継局は1個、回線は0本なので答えは \(S \times 1 = S\)。
   • \(A \neq B\) の場合、BFSで \(A\) から \(B\) へのパスを求める。具体的には、BFSの親情報を記録し、\(B\) から親を辿って \(A\) までのパスを復元する。
   • パス上の隣接する各中継局ペア \((u, v)\) について、その時点の動作モードに基づく実効座標を用いてマンハッタン距離 \(|X'_u - X'_v| + |Y'_u - Y'_v|\) を計算し、総和をとる。
   • 最終的な答えは「通信コストの総和 \(+\) \(S \times\) パス上の中継局の個数」。

計算量

• 時間計算量: \(O(Q \times N)\)
  • 各操作3でBFS（\(O(N)\)）とパス上のコスト計算（\(O(N)\)）を行う。操作1, 2は \(O(1)\)。
  • 最悪 \(Q = 5000\), \(N = 5000\) で約 \(2.5 \times 10^7\) 程度の計算量。
• 空間計算量: \(O(N)\)
  • 隣接リスト、親配列、パス配列などに \(O(N)\)。

実装のポイント

• BFSで親配列 parent を管理し、parent[v] = u（\(v\) を発見した頂点が \(u\)）と記録する。始点 \(A\) は parent[A] = A とすることで未訪問との区別を付ける。

• パスの復元は \(B\) から parent を辿って \(A\) に到達するまで繰り返す。

• 出力値が負になりうるため、符号付き整数型（long long）を使用する。

• \(S\) の値や座標値の掛け算でオーバーフローしないよう、long long 型で計算する（\(S\) は最大 \(5000 \times 10^5 = 5 \times 10^8\) 程度、ノード数との積で最大 \(2.5 \times 10^{12}\) 程度になりうる）。

  ソースコード

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<long long> X(N+1), Y(N+1);
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i];
    }
    
    vector<vector<int>> adj(N+1);
    for (int j = 0; j < N-1; j++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<bool> inverted(N+1, false);
    long long S = 0;
    
    vector<int> parent(N+1);
    
    for (int q = 0; q < Q; q++) {
        int type;
        cin >> type;
        if (type == 1) {
            int C;
            cin >> C;
            inverted[C] = !inverted[C];
        } else if (type == 2) {
            long long W;
            cin >> W;
            S += W;
        } else {
            int A, B;
            cin >> A >> B;
            
            if (A == B) {
                cout << S << "\n";
                continue;
            }
            
            // BFS from A to find path to B
            fill(parent.begin(), parent.end(), -1);
            parent[A] = A;
            queue<int> bfs;
            bfs.push(A);
            while (!bfs.empty()) {
                int u = bfs.front();
                bfs.pop();
                if (u == B) break;
                for (int v : adj[u]) {
                    if (parent[v] == -1) {
                        parent[v] = u;
                        bfs.push(v);
                    }
                }
            }
            
            // Trace path from B to A
            vector<int> path;
            int cur = B;
            while (cur != A) {
                path.push_back(cur);
                cur = parent[cur];
            }
            path.push_back(A);
            
            // Compute answer
            long long cost = 0;
            int num_nodes = (int)path.size();
            
            for (int i = 0; i + 1 < num_nodes; i++) {
                int u = path[i], v = path[i+1];
                long long xu = inverted[u] ? -X[u] : X[u];
                long long yu = inverted[u] ? -Y[u] : Y[u];
                long long xv = inverted[v] ? -X[v] : X[v];
                long long yv = inverted[v] ? -Y[v] : Y[v];
                cost += abs(xu - xv) + abs(yu - yv);
            }
            
            cost += S * (long long)num_nodes;
            
            cout << cost << "\n";
        }
    }
    
    return 0;
}

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