Counting Pairs with Given Lowest Common Ancestor

Given a tree with \(N\) nodes where the root is \(R\), and \(M\) special nodes \(P_1, P_2, \dots, P_M\), your task is to determine, for each special node \(P_i\), the number of unordered pairs of distinct nodes \((u, v)\) such that the lowest common ancestor (LCA) of \(u\) and \(v\) is exactly \(P_i\).

The lowest common ancestor of two nodes \(u\) and \(v\) in a rooted tree is defined as the deepest node that is an ancestor of both \(u\) and \(v\). For a given node \(P\), let \(S\) be the size of the subtree rooted at \(P\) and let \(s_1, s_2, \dots, s_k\) be the sizes of the subtrees rooted at each of its children. Then, the number of pairs \((u, v)\) for which \(\mathrm{LCA}(u, v) = P\) can be computed as:

$$ \text{Answer}(P) = (S - 1) + \frac{(S - 1)^2 - \sum_{i=1}^{k} s_i^2}{2}. $$

Note that in this problem every pair \((u, v)\) is considered only once (i.e. \((u, v)\) is the same as \((v, u)\)).

inputFormat

The input begins with a single line containing three integers \(N\), \(M\), and \(R\) --- the number of nodes in the tree, the number of special query nodes, and the root of the tree, respectively.

Each of the following \(N-1\) lines contains two integers \(u\) and \(v\) indicating an undirected edge between node \(u\) and node \(v\).

The last line contains \(M\) integers \(P_1, P_2, \dots, P_M\), which represent the special nodes for which you are to calculate the number of pairs \((u, v)\) whose LCA is exactly that special node.

outputFormat

Output \(M\) lines. The \(i\)th line should contain a single integer representing the number of unordered pairs \((u, v)\) (with \(u < v\)) such that \(\mathrm{LCA}(u, v) = P_i\).

sample

5 3 1
1 2
1 3
2 4
2 5
1 2 3

7
3
0