<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

507. Treediff
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Andrew has just made a breakthrough in complexity theory: he thinks that he can prove P=NP if he can get a data structure which allows to perform the following operation quickly. Naturally, you should help him complete his brilliant research. Consider a rooted tree with integers written in the leaves. For each internal (non-leaf) node v of the tree you must compute the minimum absolute difference between all pairs of numbers written in the leaves of the subtree rooted at v.
Input
The first line of the input file contains two integers n and m — overall number of nodes in the tree and number of leaves in the tree respectively. . All nodes are numbered from 1 to n. Node number 1 is always the root of the tree. Each of the other nodes has a unique parent in the tree. Each of the next n - 1 lines of the input file contains one integer — the number of the parent node for nodes 2, 3,..., n respectively. Each of the last m lines of the input file contains one integer ranging from  to  — the value of the corresponding leaf. Leaves of the tree have numbers from n - m + 1 to n.
Output
Output one line with n - m integers: for each internal node of the tree output the minimum absolute difference between pairs of values written in the leaves of its subtree. If there is only one leaf in the subtree of some internal node, output number 231 - 1 for that node. Output the answers for the nodes in order from node number 1 to n - m.
Example(s)
sample input
sample output
5 4
1
1
1
1
1 
4 
7 
9
2

sample input
sample output
5 4
1
1
1
1
1 
4 
7 
10
3

sample input
sample output
7 4
1
2
1
2
3
3
2 
10 
7 
15
3 3 8

sample input
sample output
2 1
1
100
2147483647

<|response|>
1. Abridged Problem Statement  
We have a rooted tree of n nodes (node 1 is the root) with exactly m leaves (nodes numbered n–m+1…n). Each leaf stores an integer value. For every internal node v (nodes 1…n–m), compute the minimum absolute difference |x–y| among all pairs of leaf‐values x,y in v’s subtree. If v’s subtree contains only one leaf, report 2³¹–1 (2147483647).

2. Key Observations  
• A brute‐force scan over all pairs of leaves in each subtree is O(m²) per node and too slow.  
• We can do a post‐order DFS and maintain, at each node, a set of its subtree’s leaf‐values.  
• When merging two children’s sets, always insert the smaller set into the larger (“small‐to‐large” trick) to bound total work by O(n log n) set‐operations.  
• Upon inserting a new value x into a balanced BST (e.g. std::set), we can in O(log n) find its immediate neighbors (lower_bound and predecessor) and update the minimum gap using |x–neighbor|.  
• Each leaf‐value moves O(log n) times across merges, so total complexity is O(n log² n), which is fine for n up to a few 10⁵ in 0.25 s with fast I/O.

3. Full Solution Approach  
1. Read n, m, the parent array for nodes 2…n, and the m leaf‐values (given for nodes n–m+1…n).  
2. Build the adjacency list for the tree.  
3. Initialize an array answer[1…n], defaulted to INF = 2147483647.  
4. Define a recursive DFS(u) that returns a std::set<int> S containing all leaf‐values in u’s subtree, and sets answer[u]:  
   a. If u has no children (leaf), return {leaf_value[u]}.  
   b. Otherwise, initialize an empty set S and answer[u] = INF.  
   c. For each child v of u:  
      i.  T = DFS(v).  
      ii. answer[u] = min(answer[u], answer[v]).  
      iii. If S.size() < T.size(), swap(S,T).  
      iv. For each x in T:  
           • auto it = S.lower_bound(x);  
           • If it != S.end(), answer[u] = min(answer[u], *it – x).  
           • If it != S.begin(), answer[u] = min(answer[u], x – *prev(it)).  
           • S.insert(x).  
   d. Return S.  
5. Run DFS(1).  
6. Print answer[1]…answer[n–m] separated by spaces.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;
static const int INF = 2147483647;

int n, m;
vector<vector<int>> children;
vector<int> leafValue;      // stores leaf values for nodes n-m+1…n
vector<int> answer;

// DFS returns a set of all leaf‐values in u's subtree
set<int> dfs(int u) {
    // If u is a leaf (no children), start with its own value
    if (children[u].empty()) {
        // answer[u] stays INF
        return { leafValue[u] };
    }
    // Internal node: prepare an empty set and INF answer
    set<int> S;
    answer[u] = INF;
    // Process each child
    for (int v : children[u]) {
        // Get child's set and answer
        set<int> T = dfs(v);
        // Propagate child's best gap up
        answer[u] = min(answer[u], answer[v]);
        // Always merge smaller set T into larger set S
        if (S.size() < T.size()) {
            S.swap(T);
        }
        // Insert all elements of T into S
        for (int x : T) {
            auto it = S.lower_bound(x);
            // Check the neighbor ≥ x
            if (it != S.end()) {
                answer[u] = min(answer[u], *it - x);
            }
            // Check the predecessor < x
            if (it != S.begin()) {
                answer[u] = min(answer[u], x - *prev(it));
            }
            S.insert(x);
        }
    }
    return S;
}

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

    cin >> n >> m;
    children.assign(n, {});
    leafValue.assign(n, 0);
    answer.assign(n, INF);

    // Read tree structure: parent of nodes 2..n
    for (int node = 2; node <= n; node++) {
        int p;
        cin >> p;
        // 1-based input → convert to 0-based
        children[p-1].push_back(node-1);
    }
    // Read the m leaf‐values for nodes n-m..n-1 (0-based)
    for (int i = n-m; i < n; i++) {
        cin >> leafValue[i];
    }

    // Run the DFS from root (0)
    dfs(0);

    // Output answers for internal nodes 1..n-m
    for (int i = 0; i < n-m; i++) {
        cout << answer[i] << (i+1 < n-m ? ' ' : '\n');
    }
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
import threading
from bisect import bisect_left, insort

INF = 2147483647

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n, m = map(int, (next(it), next(it)))

    # Build tree
    children = [[] for _ in range(n)]
    for node in range(2, n+1):
        p = int(next(it)) - 1
        children[p].append(node-1)

    # Read leaf values
    leaf_value = [0]*n
    for i in range(n-m, n):
        leaf_value[i] = int(next(it))

    # answer[u] = minimal gap in subtree u (INF if only one leaf)
    answer = [INF]*n

    def dfs(u):
        # If leaf, return its single value list
        if not children[u]:
            # answer[u] remains INF
            return [leaf_value[u]]

        merged = []  # this will hold the sorted leaf-values
        answer[u] = INF

        for v in children[u]:
            small = dfs(v)
            # Propagate child's answer
            answer[u] = min(answer[u], answer[v])

            # Ensure 'merged' is the larger list
            if len(merged) < len(small):
                merged, small = small, merged

            # Merge 'small' into 'merged'
            for x in small:
                idx = bisect_left(merged, x)
                # Check right neighbor
                if idx < len(merged):
                    answer[u] = min(answer[u], merged[idx] - x)
                # Check left neighbor
                if idx > 0:
                    answer[u] = min(answer[u], x - merged[idx-1])
                # Insert x to keep 'merged' sorted
                insort(merged, x)

        return merged

    dfs(0)

    # Print answers for nodes 1..n-m
    print(" ".join(str(answer[i]) for i in range(n-m)))

if __name__ == "__main__":
    # Increase recursion limit if tree is deep
    threading.stack_size(1<<25)
    sys.setrecursionlimit(1<<25)
    threading.Thread(target=main).start()
```