990. Following the Parent Pointers
Every element from 1 to n stores the number of one other element, called its
PARENT. An element whose parent is itself is a ROOT. The pointers never form a loop, so
following the chain from any element always reaches a root.
For each of q questions, print the root reached from the element given.
parents 1 1 2 3 5, ask 4 -> 1 because 4 -> 3 -> 2 -> 1
parents 1 1 2 3 5, ask 5 -> 5 because 5 is its own parent
parents 1 1 1 1 1 1, ask 6 -> 1 one step
parents 2 2, ask 1 -> 2
## The loop is obvious, the cost is not
Walking the chain is three lines. What is worth measuring is how long the chain can be.
The pointers 1 1 2 3 4 5 6 ... form a single chain of length n - 1, and asking about
the far end walks all of it. With n and q both at 2 * 10^5 that is 4 * 10^10
pointer steps.
## Path compression
After the walk has found the root r, walk the SAME chain a second time and point every
element on it straight at r.
``` r = x while parent[r] != r: r = parent[r]
while parent[x] != r: next = parent[x] parent[x] = r x = next return r ```
The second walk costs the same as the first, so one question is still O(depth), but every
element it touched now answers in a single step forever after.
## Why rewriting a pointer is safe
The only thing the pointers are ever used for is "which root does this reach". An element
x whose chain ended at r still ends at r when parent[x] is set to r directly,
and any element whose chain ran through x still ends at r too, because it now runs
through x and then one more step. Nothing else in the structure depends on the shape of
the tree, so flattening it loses no information at all.
## The saved pointer
The second walk must read parent[x] BEFORE overwriting it. Writing parent[x] = r and
then reading parent[x] to move on lands back on r immediately and stops after one
element, which compresses the first link and leaves the rest of the chain untouched. It
still prints the right answers, so the bug survives every test that only checks output and
shows up as a timeout later.
## The element that is already a root
When parent[x] == x neither loop runs and the answer is x itself. That is not a
special case to write; it is what the loop conditions already do, and a version that steps
once before checking gets it wrong.
## Cross-reference
Problem 986 interleaves merges with questions, so its pointers change while it runs. Here the pointers are handed over already built and only the compression ever rewrites them, which isolates the find from everything else.
## Cost
Time O(n + q * depth) before compression helps, and each element is flattened at most
once, so repeated questions about the same chain are nearly free. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `1 ≤ parent[i] ≤ n` - The parent pointers contain no loop, so every chain reaches a root.
Input
The first line contains two integers n and q.
The second line contains n integers, the parent of element 1, then of element 2, and so on.
Each of the next q lines contains one integer x.
Output
Print q lines. Line i holds one integer, the root reached from the ith element asked about. Print the numbers alone, one per line, with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.