{"problem":{"name":"[ICPC 2024 Xi'an I] Holes and Balls","description":{"content":"You are given $n$ balls, the $i$ -th ball's value is $p_i$. It's guaranteed that $p_1,p_2,\\dots,p_n$ is a permutation of $1,2,3\\dots,n$.                There is also a rooted tree of $n$ vertices, eac","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10560"},"statements":[{"statement_type":"Markdown","content":"You are given $n$ balls, the $i$ -th ball's value is $p_i$. It's guaranteed that $p_1,p_2,\\dots,p_n$ is a permutation of $1,2,3\\dots,n$.\n    \n    \n    \nThere is also a rooted tree of $n$ vertices, each of the vertices is a hole, and each hole can only hold one ball.\n    \n    \n    \nThe tree's root is the first vertex.\n    \n    \n    \nNow you need to fill the holes with the balls.\n    \nYou need to throw each ball in order of $1$ to $n$ in the following steps:\n\n1. Throw the ball into vertex $1$.\n2. Let the vertex where the ball is be $p$.\n3. If the $p$ -th vertex has already been filled with other balls, you need to choose a vertex $x$ and throw the ball into the $x$ -th vertex, then return to step $2$. You need to guarantee that the $x$ -th vertex is the $p$ -th vertex's son and at least one vertex in the subtree of the $x$ -th vertex is not filled.\n4. Otherwise, the ball will fill the $p$ -th vertex.\n\nAfter throwing all the balls, let $a_i$ express the value of the ball in the $i$ -th vertex.\n    \n    \n    \nYou need to find the minimum lexicographical order of $\\{a_n\\}$.\n    \n    \n    \nWe define $dep_i$ as the number of vertices on the path from the $i$ -th vertex to the tree's root(the first vertex).\n    \n    \n    \nSpecially, for any two vertices $x<y$, it's guaranteed that $dep_x\\le dep_y$.\n\n## Input\n\n    \nThe first line contains a single integer $n(1\\le n\\le 5\\times 10^5)$ - the number of vertices in this tree.\n    \n    \n    \nThe next line contains $n$ numbers, the $i$ -th number is $p_i(1\\le p_i\\le n)$. It's guaranteed that $p_1,p_2,\\dots,p_n$ is a permutation of $1,2,3\\dots,n$.\n    \n    \n    \nThe next $n-1$ lines contain a description of the tree's edges. The $i$ -th of these lines contains two integers $u_i$ and $v_i(1\\le u_i,v_i\\le n) $ - the numbers of vertices connected by the $i$ -th edge.\n    \n    \n    \nIt is guaranteed that the given edges form a tree.\n    \n    \n    \nAnd for any vertices $x<y$, it's guaranteed that $dep_x\\le dep_y$.\n\n## Output\n\nOutput $n$ integers, the minimum lexicographical order of $\\{a_n\\}$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10560","tags":["2024","O2优化","ICPC","西安"],"sample_group":[["5\n3 1 5 4 2\n1 2\n2 3\n3 4\n4 5\n","3 1 5 4 2"],["9\n9 2 6 3 5 7 1 4 8\n1 2\n1 3\n2 4\n2 5\n3 6\n3 7\n4 8\n4 9\n","9 2 1 3 6 4 8 5 7"]],"created_at":"2026-03-03 11:09:25"}}