概要

木上の2点間パスについて、「各辺のマンハッタン距離の和」と「\(S \times\) パス上の頂点数」を求める問題です。
各頂点の反転状態がクエリで変わるため、毎回その時点の状態でパスをたどって合計を計算します。

考察

この問題で重要なのは次の3点です。

1. グラフは木なので、2点間パスは一意
2. 反転操作は「その頂点の座標符号が反転するだけ」
3. 制約が \(N,Q \le 5000\) なので、1クエリ \(O(N)\) でも間に合う

---

まずクエリ 3 A B では、\(A\) から \(B\) へのパス上の辺コスト総和が必要です。
木なので、典型的には LCA（最小共通祖先）までそれぞれ登る ことでパスを処理できます。

素朴に「毎回DFSでパスを探す」とすると、実装がやや重く、毎回探索が必要です。
一方で、先に根（ここでは1）を決めて 親 parent と深さ depth を前計算しておけば、

• 深い方を同じ深さまで持ち上げる
• その後、両方を同時に親へ上げる

だけで \(A\) と \(B\) のパス辺を漏れなく数えられます。

---

反転状態については、頂点 \(i\) の実効座標を

• 通常: \((X_i,Y_i)\)
• 反転: \((-X_i,-Y_i)\)

として、その都度辺 \((u,v)\) のコスト \(|X'_u-X'_v|+|Y'_u-Y'_v|\) を計算すればOKです。
1 C クエリは flipped[C] をトグルするだけです。

---

また、答えには $\(S \times \text{(パス上の頂点数)}\)$ が加わります。
頂点数は「パスで通った辺数 + 1」なので、コードでは

• 親へ1回上がるごとに頂点カウントを増やし
• 最後にLCA分として \(+1\)

としています。
\(A=B\) のときも、辺和は0、頂点数1になり正しく処理されます。

アルゴリズム

1. 入力を受け取り、木を隣接リストで構築。
2. 頂点1を根としてBFSし、各頂点の parent と depth を前計算。
3. flipped[i]=0（全頂点通常モード）、S=0 で初期化。
4. 各クエリを処理：
   • 1 C: flipped[C] ^= 1
   • 2 W: S += W
   • 3 A B:
     1. a=A, b=B, sum_edges=0, cnt_nodes=0
     2. 深さをそろえるまで深い方を親へ上げ、そのたびに対応辺コストを加算、cnt_nodes++
     3. a!=b の間、両方を親へ上げ、2本分の辺コストを加算、cnt_nodes += 2
     4. 最後にLCA分として cnt_nodes += 1
     5. ans = sum_edges + S * cnt_nodes を出力

辺コスト計算は関数（ラムダ） edge_cost(u,v) で実装し、flipped を見て実効座標を切り替えます。

計算量

• 時間計算量:
  
  • 前計算（BFS）: \(O(N)\)
    
  • クエリ処理:
    • 1, 2 は \(O(1)\)
    • 3 は最悪で木の高さ分だけ上がるので \(O(N)\)
      
  • よって全体で \(O(N + QN)\)（最悪）
• 空間計算量: \(O(N)\)

実装のポイント

• 座標や答えは大きくなり得るため、long long を使う。

• 親配列で根の親を -1 にしているが、クエリ処理では根より上に行かない構造なので安全。

• 頂点数カウントは「上がった回数 + 1（LCA）」で管理するとバグりにくい。

• 問題文上、答えは負になり得るのでそのまま long long で出力すればよい。

  ソースコード

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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>> g(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> parent(N + 1, 0), depth(N + 1, 0);
    {
        queue<int> que;
        que.push(1);
        parent[1] = -1;
        depth[1] = 0;
        while (!que.empty()) {
            int v = que.front(); que.pop();
            for (int to : g[v]) {
                if (to == parent[v]) continue;
                parent[to] = v;
                depth[to] = depth[v] + 1;
                que.push(to);
            }
        }
    }

    vector<char> flipped(N + 1, 0);
    long long S = 0;

    auto edge_cost = [&](int u, int v) -> long long {
        long long xu = flipped[u] ? -X[u] : X[u];
        long long yu = flipped[u] ? -Y[u] : Y[u];
        long long xv = flipped[v] ? -X[v] : X[v];
        long long yv = flipped[v] ? -Y[v] : Y[v];
        return llabs(xu - xv) + llabs(yu - yv);
    };

    for (int qi = 0; qi < Q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int C;
            cin >> C;
            flipped[C] ^= 1;
        } else if (t == 2) {
            long long W;
            cin >> W;
            S += W;
        } else {
            int A, B;
            cin >> A >> B;

            long long sum_edges = 0;
            int cnt_nodes = 0;

            int a = A, b = B;
            while (depth[a] > depth[b]) {
                sum_edges += edge_cost(a, parent[a]);
                a = parent[a];
                cnt_nodes++;
            }
            while (depth[b] > depth[a]) {
                sum_edges += edge_cost(b, parent[b]);
                b = parent[b];
                cnt_nodes++;
            }
            while (a != b) {
                sum_edges += edge_cost(a, parent[a]);
                sum_edges += edge_cost(b, parent[b]);
                a = parent[a];
                b = parent[b];
                cnt_nodes += 2;
            }

            cnt_nodes += 1; // LCA
            long long ans = sum_edges + S * cnt_nodes;
            cout << ans << '\n';
        }
    }

    return 0;
}

---

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