P5002 Focus OI - Finding Ancestors

Imakf is a beginner. He has recently learned LCA. He saw a game in the mobile App Store that is also called LCA, so he downloaded it.

This game gives you a tree with $N$ nodes, where the root is $R$. The system will select $M$ nodes $P_1,P_2 \cdots P_M$, and asks Imakf to answer how many ordered pairs of nodes $(u_i, v_i)$ have their lowest common ancestor equal to $P_i$. Imakf is a beginner. Even though he has learned LCA, he still cannot solve it, so he has to ask you for help.

The first line contains three integers $N, R, M$. Then $N - 1$ lines follow, each containing two numbers $a, b$, indicating that there is an edge between $a$ and $b$. Then $1$ line follows, containing $M$ numbers, indicating $P_i$. It is guaranteed that the given edges form a tree.

Output $M$ lines in total. Each line contains one number. The number on line $i$ indicates how many ordered pairs of nodes $(u_i, v_i)$ have their lowest common ancestor equal to $P_i$.

The tree of Sample 1 is shown in the figure below:  For Query 1 $~(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,1) (2,3) (2,6) (2,7) (3,1) (3,2) (3,4) (3,5) (4,1) (4,3)$ $ (4,6) (4,7) (5,1) (5,3) (5,6) (5,7) (6,1) (6,2) (6,4) (6,5) (7,1) (7,2) (7,4) (7,5)$ there are $31$ ordered pairs in total. For Query 2 $(2,2) (2,4) (2,5) (4,2) (4,5) (5,2) (5,4)$ there are $7$ ordered pairs in total. For Query 3 $(4,4)$ there is $1$ ordered pair in total. Constraints: $1 \le R \le N \leq 10000$, $0 \le M \leq 50000$. Translated by ChatGPT 5