#P1134. 2023.03.28-第三题-塔子的有根树
2023.03.28-第三题-塔子的有根树
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
在一个偏远的山区里,有一个叫做塔子哥的数学家。他热爱数学,对树这种数据结构也有着浓厚的兴趣。
有一天,他在森林中漫步时发现了一棵美丽的大树。这棵树非常漂亮,每个节点 i 都是独特的,有着它自己的权值 vali ,并且规定 1 号点为这棵树的根节点。
塔子哥对这棵树产生了浓厚的兴趣,他开始研究这棵树的性质,并思考一些问题。他想知道如果对于树上的某个节点 t ,以 t 为根的子树中所有节点的权值都乘上一个 g ,会对整棵树产生什么影响。
为了更好地研究这个问题,他进行了 q 次操作,每次选择了一个节点 t ,并将以 t 为根的子树中所有节点的权值都乘上了一个 g 。这个过程中,他记录了每个节点的最终权值,但他还想知道一个更有趣的问题:在 q 次操作结束以后,以节点 i 为根的子树中所有节点的权值的乘积的末尾有多少个0。
这个问题非常有趣,因为它不仅涉及到树的结构,还需要考虑数学中数字的性质。塔子哥非常期待你能帮他解决这个问题。
第一行输入一个正整数n,代表这颗树的节点的数量。
第二行输入n个正整数vali,代表每个节点的权值。
接下来的n−1行,每行输入两个正整数u和v,代表节点u和节点v有一条边相连。
接下来的一行输入一个正整数q,代表操作次数。
接下来的q行,每行输入两个正整数t和g,代表塔子哥的一次操作。
1⩽n,q⩽105
1⩽vi,g⩽109
1⩽t,u,v⩽n
输出一行n个正整数,分别代表1号节点到n号节点,每个节点的子树权值乘积尾零的数量。
输入
6
1 2 3 4 5 6
1 2
2 3
1 4
2 5
4 6
2
2 5
4 5
输出
4 1 0 2 0 1
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.