给定一棵树，找到以特定节点为根的子树中两个值的乘积，使得该乘积具有最少数量的零？
Given a tree find the product of two values in the subtree rooted at a particular node such that the product has minimum number of zeros?
该问题将有 q 个查询。在每个查询中，您将在整棵树中获得一个随机节点。树的每个节点都存储一些整数值。求解器需要给出以给定节点为根的子树中任意两个节点中任意两个数的乘积后的零的最小数量。
我想到了在每个节点中存储2和5的倍数，然后自下而上计算每个节点的最小零个数。
有趣的问题，您寻找 2 和 5 的倍数的直觉是非常正确的！尾随零的数量等于两个值中的较小者。因此，例如，124000 中尾随零的数量是三个，因为 124000 = 2^5 * 5^3 * 31，由此我们得到 2^5 和 5^3，以及 min(5, 3) = 3。
这样，问题可以重述为（我将其称为P10以供进一步参考）：
P10:
Find the minimum multiplicity of either 2 or 5 in the product of
any two numbers in any two nodes in the subtree rooted at the given
node.
我准备了十个数字的例子：
让我们把数字写成因式：
好！我们已将问题处理成更可行的形式，现在我们将把它分解成更简单的形式。
首先，让我们关注一个类似的、简化的问题，不考虑五：
P2:
Find the minimum multiplicity of 2 in the product of
any two numbers in any two nodes in the subtree rooted at the given
node.
现在我们只关心twos，所以我们可以从图片中删除所有其他因素：
在这棵树中，在每个节点上，我们将从节点的子树中写下两个最小的数字，bottom-up（如您所建议的！）。在考虑一个节点时，我们已经为它的所有子节点确定了两个最小的数字，因此迭代直接子节点以找到一个节点的两个最小数字就足够了：
简化的问题解决了！只需将节点中的数字与 return 指数相乘即可：
现在上面其实已经很接近真题了(P10)。用五个而不是两个重做简化版本：
P5:
Find the minimum multiplicity of 5 in the product of
any two numbers in any two nodes in the subtree rooted at the given
node.
然后，对于任何节点 v P10 的解是 P10(v) = min(P2( v), P5(v))。
资源：
该问题将有 q 个查询。在每个查询中，您将在整棵树中获得一个随机节点。树的每个节点都存储一些整数值。求解器需要给出以给定节点为根的子树中任意两个节点中任意两个数的乘积后的零的最小数量。
我想到了在每个节点中存储2和5的倍数，然后自下而上计算每个节点的最小零个数。
有趣的问题，您寻找 2 和 5 的倍数的直觉是非常正确的！尾随零的数量等于两个值中的较小者。因此，例如，124000 中尾随零的数量是三个，因为 124000 = 2^5 * 5^3 * 31，由此我们得到 2^5 和 5^3，以及 min(5, 3) = 3。
这样，问题可以重述为（我将其称为P10以供进一步参考）：
P10:
Find the minimum multiplicity of either 2 or 5 in the product of any two numbers in any two nodes in the subtree rooted at the given node.
我准备了十个数字的例子：
让我们把数字写成因式：
好！我们已将问题处理成更可行的形式，现在我们将把它分解成更简单的形式。
首先，让我们关注一个类似的、简化的问题，不考虑五：
P2:
Find the minimum multiplicity of 2 in the product of any two numbers in any two nodes in the subtree rooted at the given node.
现在我们只关心twos，所以我们可以从图片中删除所有其他因素：
在这棵树中，在每个节点上，我们将从节点的子树中写下两个最小的数字，bottom-up（如您所建议的！）。在考虑一个节点时，我们已经为它的所有子节点确定了两个最小的数字，因此迭代直接子节点以找到一个节点的两个最小数字就足够了：
简化的问题解决了！只需将节点中的数字与 return 指数相乘即可：
现在上面其实已经很接近真题了(P10)。用五个而不是两个重做简化版本：
P5:
Find the minimum multiplicity of 5 in the product of any two numbers in any two nodes in the subtree rooted at the given node.
然后，对于任何节点 v P10 的解是 P10(v) = min(P2( v), P5(v))。
资源：