概要

木構造のネットワーク上で、各頂点の座標を通常または反転させながら、指定されたパス上の通信コストの総和を求めます。

頂点の反転状態を \(+1, -1\) の符号で管理し、各辺について「両端の符号が同じ場合」と「異なる場合」のコストをあらかじめ計算しておくことで、各クエリをパス長に比例する時間で処理します。

考察

各中継局 \(i\) のモードを符号 \(\sigma_i\) で表すことにします。

• 通常モード: \(\sigma_i = 1\)
• 反転モード: \(\sigma_i = -1\)

このとき、中継局 \(i\) の実効座標は

\[ (\sigma_i X_i, \sigma_i Y_i) \]

と表せます。

隣接する頂点 \(u, v\) の通信コストは

\[ |\sigma_u X_u - \sigma_v X_v| + |\sigma_u Y_u - \sigma_v Y_v| \]

です。

ここで重要なのは、この値は \(\sigma_u\) と \(\sigma_v\) が同じか異なるかだけで決まるという点です。

両端の符号が同じ場合

\(\sigma_u = \sigma_v\) のとき、

\[ |\sigma_u X_u - \sigma_u X_v| + |\sigma_u Y_u - \sigma_u Y_v| \]

となります。

\(\sigma_u\) は \(1\) または \(-1\) なので、絶対値の中から取り除けます。

\[ |X_u - X_v| + |Y_u - Y_v| \]

つまり、通常のマンハッタン距離です。

両端の符号が異なる場合

\(\sigma_u \neq \sigma_v\) のとき、例えば \(\sigma_u = 1, \sigma_v = -1\) とすると、

\[ |X_u + X_v| + |Y_u + Y_v| \]

になります。

逆の場合も絶対値を取るため同じ値になります。

したがって、各辺について次の \(2\) 種類の値を事前に計算できます。

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

これにより、クエリごとに座標を作り直したり、距離を毎回一から計算したりする必要がありません。

また、制約は

\[ N, Q \leq 5000 \]

なので、各クエリでパス上の辺を順にたどる \(O(N)\) の処理で十分間に合います。

木を頂点 \(1\) を根とする根付き木として扱い、各頂点の親と深さを求めておきます。

頂点 \(A\) から頂点 \(B\) へのパスを調べるときは、深い方の頂点を親方向に上げていき、深さをそろえます。その後、両方を同時に親方向へ上げていけば、最終的に LCA、つまり最小共通祖先に到達します。

このとき通った辺がちょうどパス上の辺になります。

また、クエリ 3 A B では通信コストに加えて

\[ S \times \text{パス上の頂点数} \]

を足します。

パス上の頂点数は、\(A\) と \(B\) の LCA を \(L\) とすると、

\[ \mathrm{depth}(A) + \mathrm{depth}(B) - 2 \times \mathrm{depth}(L) + 1 \]

で求められます。

アルゴリズム

まず前処理を行います。

1. 木を頂点 \(1\) を根とする根付き木として見る
2. 各頂点について、親 parent[i] と深さ depth[i] を求める
3. 各頂点 \(i \neq 1\) について、親との辺に対して以下を計算する
   • same_cost[i]
     • 頂点 \(i\) と親のモードが同じ場合のコスト
   • diff_cost[i]
     • 頂点 \(i\) と親のモードが異なる場合のコスト

具体的には、親を \(p\) とすると、

\[ \text{same\_cost}[i] = |X_i - X_p| + |Y_i - Y_p| \]

\[ \text{diff\_cost}[i] = |X_i + X_p| + |Y_i + Y_p| \]

です。

各頂点の現在のモードは sign[i] で管理します。

• 通常モード: sign[i] = 1
• 反転モード: sign[i] = -1

初期状態ではすべて通常モードなので、すべて 1 です。

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

クエリ 1 C

頂点 \(C\) のモードを反転します。

sign[C] = -sign[C]

クエリ 2 W

補正パラメータ \(S\) に \(W\) を加算します。

S += W

クエリ 3 A B

頂点 \(A\) から頂点 \(B\) までのパス上の辺をたどりながら、通信コストを合計します。

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

深さが異なる間、深い方を親に上げます。

そのとき通る辺について、子を \(x\)、親を \(p\) とすると、

• sign[x] == sign[p] なら same_cost[x]
• そうでなければ diff_cost[x]

を足します。

深さがそろったら、\(u\) と \(v\) が一致するまで、両方を同時に親に上げます。

最終的に \(u = v\) となった頂点が LCA です。

通信コストの合計を total とすると、答えは

\[ \text{total} + S \times \left(\mathrm{depth}(A) + \mathrm{depth}(B) - 2 \times \mathrm{depth}(\mathrm{LCA}) + 1\right) \]

です。

特に \(A = B\) の場合、パス上の辺は存在しないので通信コストは \(0\) です。頂点数は \(1\) なので、答えは \(S\) になります。

計算量

• 時間計算量: \(O(N + QN)\)
  • 前処理に \(O(N)\)
  • 各クエリ 3 で最大 \(O(N)\)
  • クエリ 1, 2 は \(O(1)\)
• 空間計算量: \(O(N)\)

実装のポイント

各辺のコストは、子側の頂点番号に対応させて持っています。

根を \(1\) としたとき、頂点 \(i\) の親を parent[i] とすると、辺 \((i, parent[i])\) の情報を

same_cost[i]
diff_cost[i]

に保存します。

そのため、パスを親方向にたどるときは、現在の頂点を子として扱えばよいです。

p = parent[u]

if sign[u] == sign[p]:
    total += same_cost[u]
else:
    total += diff_cost[u]

u = p

また、パス上の頂点数を求めるために、クエリ開始時の深さ

depth_sum = depth[A] + depth[B]

を保存しておきます。

最後に LCA に到達した後、

vertex_count = depth_sum - 2 * depth[lca] + 1

で頂点数を計算できます。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    N = data[idx]
    Q = data[idx + 1]
    idx += 2

    X = [0] * (N + 1)
    Y = [0] * (N + 1)
    for i in range(1, N + 1):
        X[i] = data[idx]
        Y[i] = data[idx + 1]
        idx += 2

    adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u = data[idx]
        v = data[idx + 1]
        idx += 2
        adj[u].append(v)
        adj[v].append(u)

    parent = [0] * (N + 1)
    depth = [0] * (N + 1)

    order = [1]
    for u in order:
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                depth[v] = depth[u] + 1
                order.append(v)

    same_cost = [0] * (N + 1)
    diff_cost = [0] * (N + 1)

    for i in range(2, N + 1):
        p = parent[i]
        same_cost[i] = abs(X[i] - X[p]) + abs(Y[i] - Y[p])
        diff_cost[i] = abs(X[i] + X[p]) + abs(Y[i] + Y[p])

    sign = [1] * (N + 1)
    S = 0
    out = []

    par = parent
    dep = depth
    sg = sign
    sm = same_cost
    df = diff_cost

    for _ in range(Q):
        t = data[idx]
        idx += 1

        if t == 1:
            c = data[idx]
            idx += 1
            sg[c] = -sg[c]

        elif t == 2:
            w = data[idx]
            idx += 1
            S += w

        else:
            a = data[idx]
            b = data[idx + 1]
            idx += 2

            u = a
            v = b
            du = dep[u]
            dv = dep[v]
            depth_sum = du + dv
            total = 0

            while du > dv:
                p = par[u]
                if sg[u] == sg[p]:
                    total += sm[u]
                else:
                    total += df[u]
                u = p
                du -= 1

            while dv > du:
                p = par[v]
                if sg[v] == sg[p]:
                    total += sm[v]
                else:
                    total += df[v]
                v = p
                dv -= 1

            while u != v:
                p = par[u]
                if sg[u] == sg[p]:
                    total += sm[u]
                else:
                    total += df[u]
                u = p

                p = par[v]
                if sg[v] == sg[p]:
                    total += sm[v]
                else:
                    total += df[v]
                v = p

            vertex_count = depth_sum - 2 * dep[u] + 1
            out.append(str(total + S * vertex_count))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

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