<|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++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for(auto &x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int INF = 2147483647;

int n, m;
vector<int> a;
vector<vector<int>> adj;

void read() {
    cin >> n >> m;
    a.resize(n);
    adj.assign(n, vector<int>());
    for(int i = 1; i < n; i++) {
        int par;
        cin >> par;
        adj[par - 1].push_back(i);
    }

    for(int i = 0; i < m; i++) {
        cin >> a[n - m + i];
    }
}

set<int> dfs(int u, vector<int> &answer) {
    if(adj[u].empty()) {
        return {a[u]};
    }

    set<int> s;
    for(auto v: adj[u]) {
        set<int> t = dfs(v, answer);

        answer[u] = min(answer[u], answer[v]);
        if(s.size() < t.size()) {
            swap(s, t);
        }

        for(auto x: 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);
        }
    }

    return s;
}

void solve() {
    vector<int> answer(n, INF);
    dfs(0, answer);
    for(int i = 0; i < n - m; i++) {
        cout << answer[i] << ' ';
    }
    cout << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Solution
```python
import sys
sys.setrecursionlimit(10**7)
from bisect import bisect_left, insort

INF = 2147483647

def read_input():
    data = sys.stdin.read().split()
    it = iter(data)
    n, m = map(int, (next(it), next(it)))
    # Build adjacency list
    adj = [[] for _ in range(n)]
    # Parents of nodes 2..n
    for child in range(1, n):
        p = int(next(it)) - 1
        adj[p].append(child)
    # Leaf values go into a[n-m..n-1]
    a = [0]*n
    for i in range(n-m, n):
        a[i] = int(next(it))
    return n, m, adj, a

def dfs(u, adj, a, answer):
    """
    Returns a sorted list of all leaf-values in u's subtree,
    and sets answer[u] to the minimal absolute difference found.
    """
    # If leaf, return its single-element list
    if not adj[u]:
        answer[u] = INF
        return [a[u]]

    # We'll merge children's lists into 'big'
    big = []
    answer[u] = INF

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

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

        # Merge small into big, updating answer[u]
        for x in small:
            # Locate insertion point in big
            idx = bisect_left(big, x)
            # Check right neighbor
            if idx < len(big):
                answer[u] = min(answer[u], big[idx] - x)
            # Check left neighbor
            if idx > 0:
                answer[u] = min(answer[u], x - big[idx-1])
            # Insert x into big, keeping it sorted
            insort(big, x)

    return big

def main():
    n, m, adj, a = read_input()
    answer = [INF]*n
    dfs(0, adj, a, answer)
    # Print answers for nodes 1..n-m
    out = ' '.join(str(answer[i]) for i in range(n-m))
    print(out)

if __name__ == '__main__':
    main()
```
