Overview

This is a problem about paths between two points on a tree, where we need to compute “the sum of Manhattan distances of each edge” and “\(S \times\) the number of vertices on the path.”
Since the flip state of each vertex changes with queries, we traverse the path and compute the total based on the current state each time.

Analysis

The three important points in this problem are:

1. Since the graph is a tree, the path between two points is unique
2. The flip operation simply “negates the coordinate signs of that vertex”
3. Since the constraints are \(N,Q \le 5000\), \(O(N)\) per query is fast enough

---

For query 3 A B, we need the total edge cost sum on the path from \(A\) to \(B\).
Since it’s a tree, we can typically process the path by climbing up to the LCA (Lowest Common Ancestor) from each side.

A naive approach of “finding the path via DFS each time” makes the implementation somewhat heavy and requires a search every time.
On the other hand, if we fix a root (here, vertex 1) and precompute parent parent and depth depth,

• Raise the deeper vertex to the same depth
• Then raise both simultaneously toward their parents

This alone allows us to enumerate all edges on the path from \(A\) to \(B\) without missing any.

---

Regarding the flip state, we define the effective coordinates of vertex \(i\) as:

• Normal: \((X_i,Y_i)\)
• Flipped: \((-X_i,-Y_i)\)

Then, we compute the cost of edge \((u,v)\) as \(|X'_u-X'_v|+|Y'_u-Y'_v|\) each time.
Query 1 C simply toggles flipped[C].

---

Additionally, the answer includes $\(S \times \text{(number of vertices on the path)}\)$ The number of vertices is “number of edges traversed on the path + 1”, so in the code:

• Increment the vertex count each time we move up to a parent
• Add \(+1\) at the end for the LCA

This handles the case \(A=B\) correctly as well, with edge sum being 0 and vertex count being 1.

Algorithm

1. Read input and build the tree as an adjacency list.
2. BFS from vertex 1 as root, precomputing parent and depth for each vertex.
3. Initialize flipped[i]=0 (all vertices in normal mode) and S=0.
4. Process each query:
   • 1 C: flipped[C] ^= 1
   • 2 W: S += W
   • 3 A B:
     1. a=A, b=B, sum_edges=0, cnt_nodes=0
     2. Raise the deeper vertex to its parent until depths are equal, adding the corresponding edge cost each time, cnt_nodes++
     3. While a!=b, raise both to their parents, adding edge costs for both edges, cnt_nodes += 2
     4. Finally, add cnt_nodes += 1 for the LCA
     5. Output ans = sum_edges + S * cnt_nodes

The edge cost calculation is implemented as a function (lambda) edge_cost(u,v), which checks flipped to determine the effective coordinates.

Complexity

• Time complexity:
  
  • Precomputation (BFS): \(O(N)\)
    
  • Query processing:
    • 1, 2 are \(O(1)\)
    • 3 climbs at most the height of the tree, so \(O(N)\)
      
  • Overall: \(O(N + QN)\) (worst case)
• Space complexity: \(O(N)\)

Implementation Notes

• Use long long since coordinates and answers can become large.

• The parent array sets the root’s parent to -1, but this is safe since query processing never goes above the root.

• Managing vertex count as “number of climbs + 1 (for LCA)” is less error-prone.

• According to the problem statement, the answer can be negative, so simply output it as long long.

  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, 0), depth(N + 1, 0);
    {
        queue<int> que;
        que.push(1);
        parent[1] = -1;
        depth[1] = 0;
        while (!que.empty()) {
            int v = que.front(); que.pop();
            for (int to : g[v]) {
                if (to == parent[v]) continue;
                parent[to] = v;
                depth[to] = depth[v] + 1;
                que.push(to);
            }
        }
    }

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

    auto edge_cost = [&](int u, int v) -> long long {
        long long xu = flipped[u] ? -X[u] : X[u];
        long long yu = flipped[u] ? -Y[u] : Y[u];
        long long xv = flipped[v] ? -X[v] : X[v];
        long long yv = flipped[v] ? -Y[v] : Y[v];
        return llabs(xu - xv) + llabs(yu - yv);
    };

    for (int qi = 0; qi < Q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int C;
            cin >> C;
            flipped[C] ^= 1;
        } else if (t == 2) {
            long long W;
            cin >> W;
            S += W;
        } else {
            int A, B;
            cin >> A >> B;

            long long sum_edges = 0;
            int cnt_nodes = 0;

            int a = A, b = B;
            while (depth[a] > depth[b]) {
                sum_edges += edge_cost(a, parent[a]);
                a = parent[a];
                cnt_nodes++;
            }
            while (depth[b] > depth[a]) {
                sum_edges += edge_cost(b, parent[b]);
                b = parent[b];
                cnt_nodes++;
            }
            while (a != b) {
                sum_edges += edge_cost(a, parent[a]);
                sum_edges += edge_cost(b, parent[b]);
                a = parent[a];
                b = parent[b];
                cnt_nodes += 2;
            }

            cnt_nodes += 1; // LCA
            long long ans = sum_edges + S * cnt_nodes;
            cout << ans << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.