概要

\(N\) 個の頂点からなる木構造において、頂点の「モード（通常・反転）」の切り替え、補正パラメータ \(S\) の更新、および 2 頂点間のパスにおける「通信コストの総和 + \(S \times\) 頂点数」を求める問題です。制約が \(N, Q \leq 5000\) と比較的小さいため、各クエリに対して木上の探索を行うことで解くことができます。

考察

1. 実効座標と通信コスト

各中継局 \(i\) の実効座標 \((X'_i, Y'_i)\) は、モードによって以下のように変化します。 - 通常モード： \((X_i, Y_i)\) - 反転モード： \((-X_i, -Y_i)\)

隣接する \(u, v\) 間の通信コストはマンハッタン距離 \(|X'_u - X'_v| + |Y'_u - Y'_v|\) です。モードが切り替わると、その中継局に接続されているすべての回線のコストが変化することに注意が必要です。

2. クエリの処理と制約の評価

本問題の制約は \(N, Q \leq 5000\) です。 もし \(N, Q\) が \(10^5\) クラスであれば、LCA（最小共通祖先）や樹上の累積和、あるいは Heavy-Light Decomposition などの高度なデータ構造が必要になります。しかし、今回の制約では全体の計算量が \(O(NQ)\) 程度になっても実行時間制限（通常 2 秒）に間に合います。

したがって、種類 3 のクエリ（パスの計算）が来るたびに、幅優先探索 (BFS) や深さ優先探索 (DFS) を用いて \(A\) から \(B\) へのパスを特定し、愚直にコストを計算する方針で十分です。

3. 計算式の整理

種類 3 のクエリで求める値は以下の通りです。 $\(\sum_{(u, v) \in \text{Path}} (\text{マンハッタン距離}) + S \times (\text{パス上の頂点数})\)\( パス上の頂点数を \)K\( とすると、回線（エッジ）の数は \)K-1$ 本となります。

アルゴリズム

1. 準備:
   • グラフを隣接リスト形式で保持します。
   • 各頂点の現在のモード（\(1\) または \(-1\)）を配列で管理します。
2. クエリ処理:
   • 種類 1 (1 C): mode[C] の値を反転させます（例：mode[C] *= -1）。
   • 種類 2 (2 W): 変数 \(S\) に \(W\) を加算します。
   • 種類 3 (3 A B):
     1. \(A\) を始点として BFS を行い、各頂点の「親」を記録しながら \(B\) を探します。
     2. \(B\) から親を辿って \(A\) まで戻ることで、パスを特定します。
     3. パスを辿る際、隣接する頂点間の実効座標を計算し、マンハッタン距離を合計します。
     4. 同時にパス上の頂点数 \(K\) をカウントします。
     5. (合計距離) + S * K を出力します。

計算量

• 時間計算量: \(O(Q \times N)\)
  • 各クエリにおいて、最悪の場合で木全体の探索（\(O(N)\)）を行うため、全体で \(O(QN)\) となります。
  • \(5000 \times 5000 = 2.5 \times 10^7\) 回程度の演算であり、制限時間内に十分収まります。
• 空間計算量: \(O(N)\)
  • 隣接リスト、座標データ、モード管理、探索用の配列などに必要なメモリは \(N\) に比例します。

実装のポイント

• オーバーフローへの対策: 座標や \(S\) の値、および最終的な答えは大きくなる可能性があるため、C++ では long long 型を使用してください。

• モードの管理: 通常モードを \(1\)、反転モードを \(-1\) と数値で管理すると、実効座標を X[i] * mode[i] のように簡潔に計算できます。

• パスの復元: BFS で parent[v] = u のように移動元を記録しておくことで、目的地 \(B\) から \(A\) へと逆順にパスを辿ることができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 座標やコストの計算においてオーバーフローを防ぐために long long を使用します
typedef long long ll;

// 制約に基づく中継局の最大数
const int MAXN = 5005;

// 中継局の情報を格納するためのグローバル配列
ll X[MAXN], Y[MAXN];
int mode[MAXN];
vector<int> adj[MAXN];
int parent[MAXN];
int q[MAXN];

int main() {
    // 標準入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    // N (中継局の数) と Q (操作の数) を読み込む
    if (!(cin >> N >> Q)) return 0;

    // 各中継局の基準座標を読み込む
    for (int i = 1; i <= N; ++i) {
        cin >> X[i] >> Y[i];
        // 初期状態ではすべての中継局が通常モード (1)
        mode[i] = 1;
    }

    // 木構造を形成する N-1 本の回線（エッジ）を読み込む
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 補正パラメータ S の初期値は 0
    ll S = 0;

    // Q 個の操作を順に処理する
    for (int k = 0; k < Q; ++k) {
        int type;
        cin >> type;
        if (type == 1) {
            // 操作 1: 中継局 C の動作モードを切り替える
            int C;
            cin >> C;
            mode[C] *= -1; // 1 (通常) と -1 (反転) を切り替え
        } else if (type == 2) {
            // 操作 2: S に W を加算する
            ll W;
            cin >> W;
            S += W;
        } else if (type == 3) {
            // 操作 3: A から B までのパス上の通信コストの総和 + S * (中継局の個数) を計算
            int A, B;
            cin >> A >> B;

            // 木上の唯一の単純パスを見つけるために BFS (幅優先探索) を使用
            // 各クエリごとに探索を行うため、parent 配列を初期化する
            for (int i = 1; i <= N; ++i) parent[i] = 0;
            
            int head = 0, tail = 0;
            q[tail++] = A;
            parent[A] = -1; // 開始ノードを示す特別な値

            while (head < tail) {
                int u = q[head++];
                if (u == B) break; // 目的地 B に到達したら探索終了
                for (int v : adj[u]) {
                    if (parent[v] == 0) {
                        parent[v] = u;
                        q[tail++] = v;
                    }
                }
            }

            // B から A へと親を辿り、パスを再構成しながらコストを計算する
            ll total_cost = 0;
            ll station_count = 0;
            int curr = B;
            while (curr != -1) {
                station_count++;
                int nxt = parent[curr];
                if (nxt != -1) {
                    // 現在のノード curr とその親 nxt の実効座標を計算
                    ll xu = X[curr] * mode[curr];
                    ll yu = Y[curr] * mode[curr];
                    ll xv = X[nxt] * mode[nxt];
                    ll yv = Y[nxt] * mode[nxt];
                    
                    // 実効座標間のマンハッタン距離を計算して加算
                    ll dx = xu - xv;
                    if (dx < 0) dx = -dx;
                    ll dy = yu - yv;
                    if (dy < 0) dy = -dy;
                    
                    total_cost += dx + dy;
                }
                curr = nxt;
            }
            
            // 最終的な計算結果を出力: (回線の通信コスト総和) + S * (パス上の中継局数)
            total_cost += S * station_count;
            cout << total_cost << "\n";
        }
    }

    return 0;
}

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