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 (nonleaf) 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 2
^{31}  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
