Overview

On a tree-structured network, we find the total communication cost along a specified path while each vertex’s coordinates can be in normal or inverted mode.

By managing the inversion state of each vertex as a sign of \(+1\) or \(-1\), and precomputing the cost for each edge in both cases—”both endpoints have the same sign” and “both endpoints have different signs”—we can process each query in time proportional to the path length.

Analysis

Let us represent the mode of each relay station \(i\) by a sign \(\sigma_i\).

• Normal mode: \(\sigma_i = 1\)
• Inverted mode: \(\sigma_i = -1\)

Then, the effective coordinates of relay station \(i\) can be expressed as

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

The communication cost between adjacent vertices \(u, v\) is

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

The key observation here is that this value depends only on whether \(\sigma_u\) and \(\sigma_v\) are the same or different.

When both endpoints have the same sign

When \(\sigma_u = \sigma_v\),

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

Since \(\sigma_u\) is either \(1\) or \(-1\), it can be factored out of the absolute values.

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

In other words, this is the ordinary Manhattan distance.

When both endpoints have different signs

When \(\sigma_u \neq \sigma_v\), for example if \(\sigma_u = 1, \sigma_v = -1\), we get

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

The reverse case also gives the same value due to the absolute values.

Therefore, for each edge, we can precompute the following \(2\) types of values:

• Cost when both endpoints are in the same mode
• Cost when both endpoints are in different modes

This eliminates the need to reconstruct coordinates or compute distances from scratch for each query.

Also, since the constraints are

\[ N, Q \leq 5000 \]

an \(O(N)\) traversal of edges along the path for each query is sufficiently fast.

We treat the tree as a rooted tree with vertex \(1\) as the root, and precompute the parent and depth of each vertex.

When finding the path from vertex \(A\) to vertex \(B\), we raise the deeper vertex toward its parent to equalize the depths. Then, we raise both vertices toward their parents simultaneously until they meet at the LCA (Lowest Common Ancestor).

The edges traversed during this process are exactly the edges on the path.

Additionally, for query 3 A B, we add

\[ S \times \text{number of vertices on the path} \]

to the communication cost.

The number of vertices on the path, where \(L\) is the LCA of \(A\) and \(B\), is given by

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

Algorithm

First, we perform preprocessing.

1. View the tree as a rooted tree with vertex \(1\) as the root
2. Compute the parent parent[i] and depth depth[i] for each vertex
3. For each vertex \(i \neq 1\), compute the following for the edge to its parent:
   • same_cost[i]
     • Cost when vertex \(i\) and its parent are in the same mode
   • diff_cost[i]
     • Cost when vertex \(i\) and its parent are in different modes

Specifically, if the parent is \(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| \]

The current mode of each vertex is managed by sign[i].

• Normal mode: sign[i] = 1
• Inverted mode: sign[i] = -1

In the initial state, all vertices are in normal mode, so all values are 1.

Each query is processed as follows.

Query 1 C

Invert the mode of vertex \(C\).

sign[C] = -sign[C]

Query 2 W

Add \(W\) to the correction parameter \(S\).

S += W

Query 3 A B

Traverse the edges on the path from vertex \(A\) to vertex \(B\), accumulating the communication cost.

First, set \(u = A\), \(v = B\).

While the depths differ, raise the deeper one to its parent.

For each edge traversed, letting \(x\) be the child and \(p\) be the parent:

• If sign[x] == sign[p], add same_cost[x]
• Otherwise, add diff_cost[x]

Once the depths are equal, raise both \(u\) and \(v\) to their parents simultaneously until \(u = v\).

The vertex where \(u = v\) is the LCA.

If the total communication cost is total, the answer is

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

In particular, if \(A = B\), there are no edges on the path so the communication cost is \(0\). The number of vertices is \(1\), so the answer is \(S\).

Complexity

• Time complexity: \(O(N + QN)\)
  • Preprocessing takes \(O(N)\)
  • Each query 3 takes at most \(O(N)\)
  • Queries 1 and 2 take \(O(1)\)
• Space complexity: \(O(N)\)

Implementation Details

The cost of each edge is stored indexed by the child vertex number.

When the root is \(1\) and the parent of vertex \(i\) is parent[i], the information for edge \((i, parent[i])\) is stored in

same_cost[i]
diff_cost[i]

Therefore, when traversing the path toward the parent, we simply treat the current vertex as the child.

p = parent[u]

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

u = p

Also, to compute the number of vertices on the path, we save the depths at the start of the query:

depth_sum = depth[A] + depth[B]

After reaching the LCA at the end, we can compute the vertex count as:

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

Source Code

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()

---

This editorial was generated by gpt-5.5-high.