自动搬运

查看原文

来自洛谷，原作者为

	迟暮天复明 #ee82ee

搬运于2025-08-24 22:44:13，当前版本为作者最后更新于2023-01-06 16:51:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然，每次询问的乘积可以表示成 $\dfrac{p}{q}$ 的形式。由于每一条边的边权都不超过 $4$ 位小数，所以一定可以表示成 $\dfrac{k}{10^x}$ 的形式，其中 $x$ 是小数位数。所以，如果我们想要乘积是一个整数，就必须要分子把和分母中所有的 $10$ 都约分了。

我们发现 $10=2\times5$，所以只需要分子中因数 $2$ 的个数与因数 $5$ 的个数分别大于或等于分母中因数 $2$ 和因数 $5$ 的个数即可。

我们知道每一个边权和点权都可以表示成 $2^p\times 5^q \times k$ 的形式。根据上文所说，$k$ 对解题无关紧要。所以我们可以对于每一条边和每一个点，计算出各自的 $p$ 与 $q$ 的值。那这样，我们就把问题转化为：对于每一次询问，是否对于所有要乘起来的数存在 $\sum p\ge 0$ 且 $\sum q\ge 0$。

上面的式子，我们可以分成两部分计算。一是边权的乘积，二是起始点点权。两者可以分开计算。对于起始点的点权，显然能够计算了。因此我们只需要考虑如何计算树上一条链的答案即可。

怎么计算一条链上的 $\sum p$ 和 $\sum q$ 呢？我们可以记 $f_i$ 为从树的根节点到节点 $i$ 的 $\sum p$，记 $g_i$ 为从树的根节点到节点 $i$ 的 $\sum q$。这样，就得到 $\sum p=f_u+f_v-2f_{\operatorname{lca}(u,v)},\sum q=g_u+g_v-2g_{\operatorname{lca}(u,v)}$。为了得到 $f$ 数组和 $g$ 数组的值，我们可以在计算完每一条边各自的 $p$ 和 $q$ 之后对这棵树进行一次深度优先遍历。

那么这道题就做完了。注意判断点权为 $0$ 以及边权为 $0$ 的情况。我们只要在处理的时候将 $0$ 看做 $2^{\mathrm{inf}}\times 5^{\mathrm{inf}}$ 即可。