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.
The first line is an integer T indicating the total number of testcases.
The first line of the each testcase contains two integers n and m — overall number of nodes in the tree and number of leaves in the tree respectively. 2<=n<=50000, 1<=m<n . 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 testcase contains one integer — the number of the parent node for nodes 2, 3,..., n respectively. Each of the last m lines of the testcase contains one integer ranging from -1000000 to 1000000 — the value of the corresponding leaf. Leaves of the tree have numbers from n - m + 1 to n.
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.
2 5 4 1 1 1 1 1 4 7 9 7 4 1 2 1 2 3 3 2 10 7 15
2 3 3 8
Migrated from old NTUJ.
sgu507
| No. | Testdata Range | Score |
|---|