P17283 "IXOI R2" Retribution ~ Cycle of Redemption ~


There is a rooted tree with $n$ nodes, where the node labels are $0 \sim n-1$, and the root node is labeled $r$. :::info[Some function definitions related to this problem]{open} For an array $S$, $\operatorname{mex}(S)$ denotes the smallest non-negative integer that does not appear in $S$. For example, $\operatorname{mex}(\{0,1,2,4,5\})=3$, and $\operatorname{mex}(\{\})=\operatorname{mex}(\{1,2,3\})=0$. Define $\operatorname{lca}(x,y)$ as the lowest common ancestor of nodes $x$ and $y$ in the tree. For an array $S$, $\operatorname{lcx}(S)$ is obtained by the following operations: 1. Choose all unordered pairs $(x,y)$ from $S$ (here you may choose $x=y$), and add $\operatorname{lca}(x,y)$ into an array $T$. 2. For $T$, compute $\operatorname{mex}(T)$, which is $\operatorname{lcx}(S)$. ::: Next, there are $q$ **independent** queries. You need to choose some numbers from $0 \sim n-1$ and put them into an array $H$. In each query, you are given a parameter $x$, meaning you must choose at least $x$ **distinct** numbers to put into $H$. Among all $H$ that satisfy the requirement, find the minimum possible value of $\operatorname{lcx}(H)$.

The first line contains three integers $n,q,r$. The next $n-1$ lines each contain two integers $u,v$, indicating an edge in the tree. The next $q$ lines each contain one integer $x$, which is the parameter of the query.

Output $q$ lines, each containing one integer. The integer on line $i$ is the answer to the $i$-th query.

### Sample Explanation For the first query, one valid choice is $H=\{0,1,2,3,4,5,6,7,8\}$. Then $\operatorname{lcx}(H)=9$. It can be proven that there is no better choice. For the sixth query, when $H=\{3,4,5,6\}$, we have $\operatorname{lcx}(H)=0$. It can be proven that there is no better choice. ### Constraints **This problem uses bundled testdata**. |Subtask|$n\le$|Special property|Score| |:-:|:-:|:-:|:-:| |$1$|$10$|None|$10$| |$2$|$10^3$|None|$25$| |$3$|$10^6$|$r=1$ and node $0$ is directly connected to all other nodes|$25$| |$4$|$10^6$|None|$40$| For all testdata, it is guaranteed that $0\le u,v,r