Overview

In a tree structure consisting of \(N\) vertices, we need to handle toggling vertex “modes (normal/inverted),” updating a correction parameter \(S\), and computing “the sum of communication costs along the path between two vertices + \(S \times\) number of vertices.” Since the constraints are relatively small at \(N, Q \leq 5000\), this can be solved by performing a tree traversal for each query.

Analysis

1. Effective Coordinates and Communication Cost

The effective coordinates \((X'_i, Y'_i)\) of each relay station \(i\) change depending on the mode as follows: - Normal mode: \((X_i, Y_i)\) - Inverted mode: \((-X_i, -Y_i)\)

The communication cost between adjacent vertices \(u, v\) is the Manhattan distance \(|X'_u - X'_v| + |Y'_u - Y'_v|\). Note that when a mode is toggled, the costs of all links connected to that relay station change.

2. Query Processing and Constraint Evaluation

The constraints of this problem are \(N, Q \leq 5000\). If \(N, Q\) were on the order of \(10^5\), advanced data structures such as LCA (Lowest Common Ancestor), prefix sums on trees, or Heavy-Light Decomposition would be necessary. However, with the given constraints, an overall time complexity of around \(O(NQ)\) fits within the time limit (typically 2 seconds).

Therefore, each time a type 3 query (path computation) arrives, it is sufficient to identify the path from \(A\) to \(B\) using Breadth-First Search (BFS) or Depth-First Search (DFS) and compute the cost directly.

3. Organizing the Formula

The value to compute for a type 3 query is as follows: $\(\sum_{(u, v) \in \text{Path}} (\text{Manhattan distance}) + S \times (\text{number of vertices on the path})\)\( If the number of vertices on the path is \)K\(, then the number of edges is \)K-1$.

Algorithm

1. Preparation:
   • Store the graph in adjacency list format.
   • Manage the current mode of each vertex (\(1\) or \(-1\)) using an array.
2. Query Processing:
   • Type 1 (1 C): Invert the value of mode[C] (e.g., mode[C] *= -1).
   • Type 2 (2 W): Add \(W\) to the variable \(S\).
   • Type 3 (3 A B):
     1. Perform BFS starting from \(A\), recording the “parent” of each vertex while searching for \(B\).
     2. Trace back from \(B\) to \(A\) by following parent pointers to identify the path.
     3. While traversing the path, compute the effective coordinates of adjacent vertices and sum up the Manhattan distances.
     4. Simultaneously count the number of vertices \(K\) on the path.
     5. Output (total distance) + S * K.

Complexity

• Time Complexity: \(O(Q \times N)\)
  • For each query, in the worst case, a traversal of the entire tree (\(O(N)\)) is performed, resulting in an overall complexity of \(O(QN)\).
  • This amounts to approximately \(5000 \times 5000 = 2.5 \times 10^7\) operations, which comfortably fits within the time limit.
• Space Complexity: \(O(N)\)
  • The memory required for the adjacency list, coordinate data, mode management, and traversal arrays is proportional to \(N\).

Implementation Notes

• Overflow prevention: Coordinates, the value of \(S\), and the final answer can become large, so use the long long type in C++.

• Mode management: By representing normal mode as \(1\) and inverted mode as \(-1\) numerically, effective coordinates can be computed concisely as X[i] * mode[i].

• Path reconstruction: By recording the predecessor as parent[v] = u during BFS, the path can be traced in reverse from destination \(B\) back to \(A\).

  Source Code

#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;
}

This editorial was generated by gemini-3-flash-thinking.