一切都已过去

迟暮天复明 · 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}} 即可。