U387235 lca
题目描述
现在有一棵有 $n$ 个节点的有根树，根节点始终是 $1$，现在定义了一个表达式
$$
f(x) = \prod_{i = 1}^{n} lca(x, i)
$$
$lca(u,v)$ 代表节点 $u$ 和节点 $v$ 之间的公共祖先节点编号。
现在给定一个正整数 $x$，请输出对应的 $f(x)$ 答案的后缀 $0$ 的个数。
输入格式
第一行包括两个整数 $n$ 和 $q$，分别代表树的大小和查询的次数。
接下来的 $n - 1$ 行, 每行包括两个整数，$u$ 和 $v$ ($1 \le u,v \le n,u\ne v$),
其中 $u$ 和 $v$ 分别代表无向边的两个端点，数据确保所有的边构建起来能够是一棵树。
接下来给出 $q$ 组询问，每组询问包括一个整数 $x$ ($1 \le x \le n$)。
输出格式
对于每一组询问，输出一个整数并换行代表答案。
说明/提示
### 样例一解释
当 $x = 1$ 的时候，任何点和 $1$ 节点的 $lca$ 都是 $1$， 乘积答案就是 $1$ ， 不存在后缀 $0$ 。
当 $x = 2$ 的时候：
$lca(2, 1) = 1$ ，
$lca(2, 2) = 2$ ，
$lca(2, 3) = 2$ ，
$lca(2, 4) = 5$ ，
$lca(2, 5) = 5$ ，
$f(2) = \prod_{i = 1}^{n} lca(2, i) = 100$ 。
当 $x = 3$ 的时候：
$lca(3, 1) = 1$ ，
$lca(3, 2) = 2$ ，
$lca(3, 3) = 3$ ，
$lca(3, 4) = 5$ ，
$lca(3, 5) = 5$ ，
$f(3) = \prod_{i = 1}^{n} lca(3, i) = 150$ 。
当 $x = 4$ 的时候：
$lca(4, 1) = 1$ ，
$lca(4, 2) = 5$ ，
$lca(4, 3) = 5$ ，
$lca(4, 4) = 4$ ，
$lca(4, 5) = 5$ ，
$f(4) = \prod_{i = 1}^{n} lca(4, i) = 500$ 。
当 $x = 5$ 的时候：
$lca(5, 1) = 1$ ，
$lca(5, 2) = 5$ ，
$lca(5, 3) = 5$ ，
$lca(5, 4) = 5$ ，
$lca(5, 5) = 5$ ，
$f(5) = \prod_{i = 1}^{n} lca(5, i) = 625$ 。
对于 $50 \%$ 的数据范围，$1 \le n \le 1000, 1 \le q \le 1000$。
对于$100 \%$ 的数据范围，$1 \le n \le 10^5, 1 \le q \le 10^5$。