In a tree-structured neighborhood where the root represents the delivery station, a courier must visit all requested delivery nodes at least once. The goal is to compute, after each new delivery request, the shortest total distance required to deliver all orders so far—without needing to return to the root.

The key insight is that traversing all required nodes in a tree requires walking each edge twice (once going down, once coming back), except for the path from the root to the deepest visited node, which only needs to be traversed once (since we don't return). Thus, the minimal distance is:

2 × (number of edges in the induced subtree) − (depth of the deepest visited node)

Since each edge has unit length and the induced subtree consists of all ancestors of the requested nodes, we can maintain:

• A visited marker for each node.
• The total number of newly activated edges (each contributes 2 to the round-trip cost).
• The maximum depth among all visited delivery nodes.

When a new delivery node is added, we traverse upward toward the root until we hit an already visited ancestor. Each unvisited node along this path increments the edge count by 1 (hence +2 to total distance). Simultaneously, we update the maximum depth.

Note: The root is the node whose parent is -1; its not necessarily node 1.

Implementation Strategy

1. Read the parent array and identify the root.
2. Precompute the depth of every node (distance from root, with root depth = 1).
3. Maintain a boolean array to track visited nodes.
4. For each query:
   • If the node is already visited, output the current result unchanged.
   • Otherwise, climb up the tree until reaching a visited node, marking new nodes as visited and adding 2 per new edge.
   • Update the maximum depth seen so far.
   • Output total_distance − max_depth + 1 (since depth is 1-indexed).

Corrected Reference Code (DFS-based Depth Calculation)

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100010;

int n, m, root;
int parent[MAXN], visited[MAXN], depth[MAXN];
long long total_edges = 0;
int max_depth = 1;

// Compute depth recursively with memoization
int get_depth(int u) {
    if (depth[u] != 0) return depth[u];
    depth[u] = get_depth(parent[u]) + 1;
    return depth[u];
}

// Activate path from u up to first visited ancestor
void activate(int u) {
    if (visited[u]) return;
    visited[u] = 1;
    total_edges++;
    activate(parent[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> parent[i];
        if (parent[i] == -1) {
            root = i;
            depth[root] = 1;
        }
    }

    // Precompute depths for all nodes
    for (int i = 1; i <= n; ++i) {
        if (depth[i] == 0) {
            get_depth(i);
        }
    }

    visited[root] = 1;

    while (m--) {
        int x;
        cin >> x;
        if (!visited[x]) {
            activate(x);
        }
        if (depth[x] > max_depth) {
            max_depth = depth[x];
        }
        cout << 2 * total_edges - max_depth + 1 << '\n';
    }

    return 0;
}