Overview

This problem requires computing the sum of edge costs along a path on a tree based on the current flip state of each vertex, plus an addition from the correction value \(S\).

We utilize the fact that the communication cost of each edge is determined solely by whether the flip states of its two endpoints are the same or different.

Analysis

The effective coordinates of vertex \(i\) are \((X_i, Y_i)\) in normal mode and \((-X_i, -Y_i)\) in flipped mode.

Now, let’s consider the communication cost between adjacent vertices \(u, v\).

When both endpoints have the same mode

If both are in normal mode:

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

If both are in flipped mode:

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

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

That is, when both endpoints have the same mode, the communication cost is always:

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

When the endpoints have different modes

If one is normal and the other is flipped, for example \(u\) is normal and \(v\) is flipped:

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

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

The reverse case yields the same value.

Therefore, for each edge, it suffices to precompute two types of costs:

• Cost when both endpoints have the same mode
• Cost when both endpoints have different modes

---

A naive approach would be to find the path for each query and compute the distance by flipping coordinates on the spot each time, but splitting the formula based on flip states every time becomes complex.

In this solution, we treat the tree as a rooted tree and manage each edge as “an edge connecting a parent and child.”

For the edge connecting vertex \(v\) and its parent \(parent[v]\), we store:

• \(sameCost[v]\): cost when both endpoints have the same mode
• \(diffCost[v]\): cost when both endpoints have different modes

Given the current flip state flipped[i], the current cost of edge \((parent[v], v)\) is:

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

Also, for type \(3\) queries, the number of vertices on the path is needed.

If the path on the tree has \(k\) edges, then the number of vertices is \(k + 1\).

Therefore, if the sum of edge costs on the path is \(sum\) and the number of edges is \(edges\), the answer is:

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

Algorithm

First, we root the tree at vertex \(1\).

Using BFS or DFS, we compute the following for each vertex:

• parent[v]: parent of vertex \(v\)
• depth[v]: depth from the root
• sameCost[v]: cost of edge \((parent[v], v)\) when both endpoints have the same mode
• diffCost[v]: cost of edge \((parent[v], v)\) when both endpoints have different modes

Specifically, with parent \(u\) and child \(v\):

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

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

---

Each query is processed as follows:

Type \(1\): 1 C

Toggle the flip state of vertex \(C\).

flipped[C] ^= 1;

Type \(2\): 2 W

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

S += W;

Type \(3\): 3 A B

Traverse the path from vertex \(A\) to vertex \(B\), computing the sum of edge costs and the number of edges.

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

1. Move the deeper vertex up to its parent, adding the cost of each traversed edge
2. Once the depths are equal, move \(u\) and \(v\) up to their parents simultaneously, adding both edge costs
3. The point where \(u = v\) is the LCA
4. If the number of edges is \(edges\), then the number of vertices is \(edges + 1\)
5. The answer is \(sum + S \times (edges + 1)\)

The current cost of edge \((parent[x], x)\) is computed as follows:

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

Since \(N, Q \leq 5000\) in this problem, an \(O(N)\) process that traverses the path one edge at a time is fast enough.

Complexity

• Time complexity: \(O(N + NQ)\)
  • Preprocessing is \(O(N)\)
  • Each type \(3\) query takes \(O(N)\) in the worst case
  • Type \(1\) and \(2\) queries are \(O(1)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Storing edge information on the “child side vertex” makes it easy to handle.

  • sameCost[v], diffCost[v] correspond to edge \((parent[v], v)\).

• Vertex \(1\) (the root) has no parent, but this is not a problem since we never go above the root when traversing a path.

• The answer can become large, and \(S\) can become negative, so use long long.

• When \(A = B\), the number of edges on the path is \(0\) and the number of vertices is \(1\), so the answer is \(S\). The code naturally handles this case as well.

  Source Code

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

---

This editorial was generated by gpt-5.5-xhigh.