小红获得一棵节点数为 n 的树,节点编号为 1,2,…,n ,其中第 i 个节点的权值为 ai 定义一个连通块为"好连通块":该连通块中所有节点的点权乘积尾数存在0 。
求好连通块的个数,结果对 109+7 取模。
对于树上的任意一个点集 S,如果点集中的仼意两点 u,v 满足" u 到 v 的简单路径上的所有点都在点集中",则称 S 是一个连通块。特别地,单独的点也构成一个连通块。
给定一棵节点数为 n 的树,节点编号为 1,2,…,n,每个节点的权值为 ai。我们定义一个连通块为“好连通块”,当且仅当该连通块中所有节点的权值的乘积的末尾至少有一个零。也就是说,乘积中包含因子 2 和 5 各至少一个。
求树上所有“好连通块”的个数,结果对 109+7 取模。