The problem presents a scenario involving a delivery network modeled as a tree structure. The network consists of N nodes (locations) connected by N-1 bidirectional roads, with no cycles. One specific node serves as the root (the delivery station). The goal is to determine the minimum distance required to visit all currently active delivery locations starting from the station. Crucially, after the last delivery, the driver does not need to return to the station.

The challenge is to handle this dynamical: as new delivery orders (nodes) are added one by one, we must calculate the updated minimum distance immediately after each addition.

Algorithmic Approach

Since the underlying graph is a tree, there is exactly one unique path between any two nodes. If we were required to return to the starting point (the station) after visiting all active nodes, the total distance would simply be twice the number of edges in the connected subgraph containing the root and all active nodes (since every edge must be traversed twice: once to go down, once to come back up).

However, the "no return" requirement allows us to optimize the path. The optimal route involves traversing every edge in the active subgraph twice, except for the edges along the single longest path from the root to the furthest active node. On this longest path, we only traverse the edges once (going down).

Therefore, the formula for the minimum distance is:

Min Distance = (2 × Total Edges in Active Subgraph) - (Distance to Furthest Node)

When a new node X is added to the order list:

1. Update Subgraph: Identify the path from X back to the nearest node already in the active subgraph (or the root). Let the length of this path be L. This adds L new edges to our subgraph.
2. Update Round Trip Cost: The cost to visit these new nodes and return to the existing network incresaes by 2 × L.
3. Update Max Depth: Compare the depth of node X with the current maximum depth from the root.
4. Calculate Result: Apply the formula: Total Round Trip Cost - Max Depth + 1 (assuming 1-based depth indexing, so distance is depth - 1).

Input/Output Specification

Input:

• First line: Two integers N (total nodes) and M (number of new orders).
• Second line: N integers representing the parent of each node (1 to N). The root's parent is -1.
• Next M lines: Each line contains an integer X_i, representing a new delivery location.

Output:

• For each new order, print the calculated minimum distance to visit all active nodes.

Sample Input

7 4
-1 1 1 1 2 2 3
5
6
2
4

Sample Output

2
4
4
6

Implementation

We can solve this efficiently using a Breadth-First Search (BFS) to pre-calculate the depth of every node from the root. We maintain an array to track which nodes are currently part of the delivery route. For each query, we traverse upwards from the target node until we find a visited node, marking all intermediate nodes as visited and accumulating the distance. The total complexity is linear O(N + M) because each edge is processed at most once.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_NODES = 1e5 + 5;

int main() {
    // Optimize I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numNodes, numOrders;
    if (!(cin >> numNodes >> numOrders)) return 0;

    int parent[MAX_NODES];
    int depth[MAX_NODES];
    bool isVisited[MAX_NODES] = {false};
    vector<int> children[MAX_NODES];

    int root = -1;
    for (int i = 1; i <= numNodes; ++i) {
        cin >> parent[i];
        if (parent[i] == -1) {
            root = i;
        } else {
            children[parent[i]].push_back(i);
        }
    }

    // BFS to calculate depth of each node from the root
    queue<int> q;
    q.push(root);
    depth[root] = 1;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        for (int child : children[curr]) {
            depth[child] = depth[curr] + 1;
            q.push(child);
        }
    }

    long long roundTripCost = 0;
    isVisited[root] = true;
    int maxDepth = 0;

    // Process each new order
    for (int i = 0; i < numOrders; ++i) {
        int target;
        cin >> target;

        // Update the furthest distance from root
        maxDepth = max(maxDepth, depth[target]);

        // Traverse up to find the nearest visited node
        int currNode = target;
        while (!isVisited[currNode]) {
            isVisited[currNode] = true;
            roundTripCost += 2; // Add cost for going down and up the edge
            currNode = parent[currNode];
        }

        // Minimum distance is total round trip minus the longest one-way path
        // Since depth is 1-based, actual distance is depth - 1
        cout << roundTripCost - maxDepth + 1 << "\n";
    }

    return 0;
}