概要

木上のパスについて、現在の各頂点の反転状態に応じた辺コストの合計と、補正値 \(S\) による加算分を求める問題です。

各辺について「両端の反転状態が同じか異なるか」だけで通信コストが決まることを利用します。

考察

頂点 \(i\) の実効座標は、通常モードなら \((X_i, Y_i)\)、反転モードなら \((-X_i, -Y_i)\) です。

ここで、隣接する頂点 \(u, v\) の通信コストを考えます。

両端のモードが同じ場合

両方通常なら、

\(|X_u - X_v| + |Y_u - Y_v|\)

です。

両方反転なら、

\(|-X_u - (-X_v)| + |-Y_u - (-Y_v)|\)

\(= |X_u - X_v| + |Y_u - Y_v|\)

となります。

つまり、両端のモードが同じなら、通信コストは常に

\(|X_u - X_v| + |Y_u - Y_v|\)

です。

両端のモードが異なる場合

一方が通常、もう一方が反転なら、例えば \(u\) が通常、\(v\) が反転として、

\(|X_u - (-X_v)| + |Y_u - (-Y_v)|\)

\(= |X_u + X_v| + |Y_u + Y_v|\)

です。

逆の場合も同じ値になります。

したがって、各辺について事前に

• 両端のモードが同じ場合のコスト
• 両端のモードが異なる場合のコスト

の \(2\) 種類を計算しておけば十分です。

---

素朴に、各クエリごとにパスを探して、その場で毎回座標を反転して距離を計算してもよいですが、反転状態によって式を毎回分けて考えると複雑になります。

この解法では、木を根付き木として扱い、各辺を「親と子を結ぶ辺」として管理します。

頂点 \(v\) とその親 \(parent[v]\) を結ぶ辺について、

• \(sameCost[v]\) : 両端のモードが同じ場合のコスト
• \(diffCost[v]\) : 両端のモードが異なる場合のコスト

を持っておきます。

現在の反転状態を flipped[i] とすると、辺 \((parent[v], v)\) の現在のコストは、

• flipped[v] ^ flipped[parent[v]] == 0 なら \(sameCost[v]\)
• flipped[v] ^ flipped[parent[v]] == 1 なら \(diffCost[v]\)

になります。

また、種類 \(3\) のクエリでは、パス上の頂点数も必要です。

木のパスで辺数が \(k\) 本なら、頂点数は \(k + 1\) 個です。

そのため、パス上の辺コストの合計を \(sum\)、辺数を \(edges\) とすると、答えは

\(sum + S \times (edges + 1)\)

です。

アルゴリズム

まず、木を頂点 \(1\) を根とする根付き木にします。

BFS または DFS により、各頂点について以下を求めます。

• parent[v] : 頂点 \(v\) の親
• depth[v] : 根からの深さ
• sameCost[v] : 辺 \((parent[v], v)\) の、両端のモードが同じ場合のコスト
• diffCost[v] : 辺 \((parent[v], v)\) の、両端のモードが異なる場合のコスト

具体的には、親を \(u\)、子を \(v\) とすると、

\(sameCost[v] = |X_u - X_v| + |Y_u - Y_v|\)

\(diffCost[v] = |X_u + X_v| + |Y_u + Y_v|\)

です。

---

各クエリは次のように処理します。

種類 \(1\) : 1 C

頂点 \(C\) の反転状態を切り替えます。

flipped[C] ^= 1;

種類 \(2\) : 2 W

補正値 \(S\) に \(W\) を加算します。

S += W;

種類 \(3\) : 3 A B

頂点 \(A\) から頂点 \(B\) までのパスをたどり、辺コストの合計と辺数を求めます。

まず \(u = A\), \(v = B\) とします。

1. 深い方の頂点を親へ上げながら、通った辺のコストを足す
2. 深さが同じになったら、\(u\) と \(v\) を同時に親へ上げながら、両方の辺コストを足す
3. \(u = v\) になったところが LCA
4. 辺数を \(edges\) とすると、頂点数は \(edges + 1\)
5. 答えは \(sum + S \times (edges + 1)\)

辺 \((parent[x], x)\) の現在のコストは、次のように求めます。

if (flipped[x] ^ flipped[parent[x]]) {
    cost = diffCost[x];
} else {
    cost = sameCost[x];
}

この問題では \(N, Q \leq 5000\) なので、パスを \(1\) 辺ずつたどる \(O(N)\) の処理で十分間に合います。

計算量

• 時間計算量: \(O(N + NQ)\)
  • 前処理が \(O(N)\)
  • 各種類 \(3\) クエリで最悪 \(O(N)\)
  • 種類 \(1\), \(2\) クエリは \(O(1)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 辺の情報は「子側の頂点」に持たせると扱いやすいです。

  • sameCost[v], diffCost[v] は辺 \((parent[v], v)\) に対応します。

• 根である頂点 \(1\) には親が存在しませんが、パスをたどる際に根からさらに上へ行くことはないため問題ありません。

• 答えは大きくなる可能性があり、また \(S\) が負になることもあるため、long long を使います。

• \(A = B\) の場合、パス上の辺数は \(0\)、頂点数は \(1\) なので、答えは \(S\) になります。コード中の処理でも自然にこのケースを扱えます。

  ソースコード

#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, -1), depth(N + 1, 0);
    vector<long long> sameCost(N + 1, 0), diffCost(N + 1, 0);

    queue<int> que;
    parent[1] = 0;
    que.push(1);

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (int v : g[u]) {
            if (parent[v] != -1) continue;

            parent[v] = u;
            depth[v] = depth[u] + 1;

            sameCost[v] = llabs(X[u] - X[v]) + llabs(Y[u] - Y[v]);
            diffCost[v] = llabs(X[u] + X[v]) + llabs(Y[u] + Y[v]);

            que.push(v);
        }
    }

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

    auto edgeCost = [&](int v) -> long long {
        return (flipped[v] ^ flipped[parent[v]]) ? diffCost[v] : sameCost[v];
    };

    for (int qi = 0; qi < Q; qi++) {
        int type;
        cin >> type;

        if (type == 1) {
            int C;
            cin >> C;
            flipped[C] ^= 1;
        } else if (type == 2) {
            long long W;
            cin >> W;
            S += W;
        } else {
            int A, B;
            cin >> A >> B;

            int u = A, v = B;
            long long sum = 0;
            int edges = 0;

            while (depth[u] > depth[v]) {
                sum += edgeCost(u);
                u = parent[u];
                edges++;
            }

            while (depth[v] > depth[u]) {
                sum += edgeCost(v);
                v = parent[v];
                edges++;
            }

            while (u != v) {
                sum += edgeCost(u);
                sum += edgeCost(v);
                u = parent[u];
                v = parent[v];
                edges += 2;
            }

            long long ans = sum + S * (edges + 1LL);
            cout << ans << '\n';
        }
    }

    return 0;
}

---

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