Background

Problem Description

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)$.

Input Format

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 Format

Output $q$ lines, each containing one integer.

The integer on line $i$ is the answer to the $i$-th query.

9 6 2
4 5
4 6
4 0
1 0
1 7
1 8
2 0
2 3
9
8
7
6
5
4

9
3
1
1
0
0

Hint

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.

For all testdata, it is guaranteed that $0\le u,v,r<n\le 10^6$, $1\le q\le 10^6+1$, and $0\le x\le n$.

Translated by ChatGPT 5