{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":" Andrew has just made a breakthrough in complexity theory: he thinks that he can prove \n \u003ci\u003eP\u003c/i\u003e\u003dNP 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 \n \u003ci\u003ev\u003c/i\u003e of the tree you must compute the minimum absolute difference between all pairs of numbers written in the leaves of the subtree rooted at \n \u003ci\u003ev\u003c/i\u003e. \n\u003cbr\u003e对于每个非叶子节点,在子树中找到两个叶子节点使得它们的权值之差的绝对值最小。如果子树内只有一个节点。输出2\u003csup\u003e31\u003c/sup\u003e-1\n \u003cbr\u003e\n \u003cdiv align\u003d\"left\" style\u003d\"margin-top:1em;\"\u003e\n \u003cb\u003eInput\u003c/b\u003e\n \u003c/div\u003eThe first line of the input file contains two integers \n \u003ci\u003en\u003c/i\u003e and \n \u003ci\u003em\u003c/i\u003e\u0026nbsp;— overall number of nodes in the tree and number of leaves in the tree respectively. \n\u003cbr\u003e\n \u003cimg style\u003d\"vertical-align:text-bottom;position:relative;top:-2px;\" SRC\u003d\"CDN_BASE_URL/e5ec3a980823550c92fd17ae87e5b45d?v\u003d1533129061\"\u003e.\n\u003cbr\u003e 第一行两个整数,n和m,表示树的大小和叶子的个数。树的根永远是1.\n\u003cbr\u003eAll nodes are numbered from 1 to \n \u003ci\u003en\u003c/i\u003e. 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 \u003ci\u003en\u003c/i\u003e - 1 lines of the input file contains one integer\u0026nbsp;— the number of the parent node for nodes 2, 3,..., \n \u003ci\u003en\u003c/i\u003e respectively. \n\u003cbr\u003e接下来n-1行,表示2-n的父亲节点。\nEach of the last \n \u003ci\u003em\u003c/i\u003e lines of the input file contains one integer ranging from \n \u003cimg style\u003d\"vertical-align:text-bottom;position:relative;top:-2px;\" SRC\u003d\"CDN_BASE_URL/0b610887d7538cccd29a1a1e6dddaa55?v\u003d1533129061\"\u003e to \n \u003cimg style\u003d\"vertical-align:text-bottom;position:relative;top:-2px;\" SRC\u003d\"CDN_BASE_URL/3ccb2210355d754e152ee25f696c6b0f?v\u003d1533129061\"\u003e — the value of the corresponding leaf. Leaves of the tree have numbers from \n \u003ci\u003en\u003c/i\u003e - \n \u003ci\u003em\u003c/i\u003e + 1 to \n \u003ci\u003en\u003c/i\u003e. \n \u003cbr\u003e\n\u003cbr\u003e最后m行,表示叶子的权值。叶子节点的编号是从n-m+1到n\n \u003cdiv align\u003d\"left\" style\u003d\"margin-top:1em;\"\u003e\n \u003cb\u003eOutput\u003c/b\u003e\n \u003c/div\u003eOutput one line with \n \u003ci\u003en\u003c/i\u003e - \n \u003ci\u003em\u003c/i\u003e 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\n \u003csup\u003e31\u003c/sup\u003e - 1 for that node. Output the answers for the nodes in order from node number 1 to \n \u003ci\u003en\u003c/i\u003e - \n \u003ci\u003em\u003c/i\u003e. \n \u003cbr\u003e\n\u003cbr\u003e输出n-m行,表示每个非叶子节点对应的答案。\n \u003cdiv align\u003d\"left\" style\u003d\"margin-top:1em;\"\u003e\n \u003cb\u003eExample(s)\u003c/b\u003e\n \u003c/div\u003e \n \u003ctable cellspacing\u003d\"0\" cellpadding\u003d\"4\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample input\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample output\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e5 4\n1\n1\n1\n1\n1 \n4 \n7 \n9\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e2\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003cbr\u003e \n \u003ctable cellspacing\u003d\"0\" cellpadding\u003d\"4\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample input\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample output\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e5 4\n1\n1\n1\n1\n1 \n4 \n7 \n10\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e3\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003cbr\u003e \n \u003ctable cellspacing\u003d\"0\" cellpadding\u003d\"4\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample input\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample output\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e7 4\n1\n2\n1\n2\n3\n3\n2 \n10 \n7 \n15\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e3 3 8\n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003cbr\u003e \n \u003ctable cellspacing\u003d\"0\" cellpadding\u003d\"4\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \n \u003ctbody\u003e\n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample input\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003esample output\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003ctr\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e2 1\n1\n100\n\u003c/pre\u003e \u003c/td\u003e \n \u003ctd width\u003d\"400\" valign\u003d\"top\" style\u003d\"border-collapse:collapse; border: 1px black solid;\"\u003e \u003cpre\u003e2147483647 \n\u003c/pre\u003e \u003c/td\u003e \n \u003c/tr\u003e \n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003cbr\u003e \n \u003c/div\u003e\n "}}]}