第2题-塔子的有根树

ID: 138

Type: Default

1500ms

256MiB

Difficulty: 7

Uploaded By:

Tags>

百度

题目内容

在一个偏远的山区里，有一个叫做塔子哥的数学家。他热爱数学，对树这种数据结构也有着浓厚的兴趣。

有一天，他在森林中漫步时发现了一棵美丽的大树。这棵树非常漂亮，每个节点 $i$ 都是独特的，有着它自己的权值 $val_i$ ，并且规定 $1$ 号点为这棵树的根节点。

塔子哥对这棵树产生了浓厚的兴趣，他开始研究这棵树的性质，并思考一些问题。他想知道如果对于树上的某个节点 $t$ ，以 $t$ 为根的子树中所有节点的权值都乘上一个 $g$ ，会对整棵树产生什么影响。

1.末尾的0

某个数 $x$ 的末尾0的个数等价于 $x$ 质因分解后 $2,5$ 的个数中的较小值。所以我们去记录每个节点的权值中2的个数以及5的个数即可。

例如: $25000 = 2^3 * 5^5$ , 所以它末尾有 $min(3,5)=3$ 个0