题解
题目描述
给定一棵节点数为 n 的树，节点编号为 1,2,…,n，每个节点的权值为 ai。我们定义一个连通块为“好连通块”，当且仅当该连通块中所有节点的权值的乘积的末尾至少有一个零。也就是说，乘积中包含因子 2 和 5 各至少一个。
求树上所有“好连通块”的个数，结果对 109+7 取模。
连通块定义
题目内容
小红获得一棵节点数为 n 的树，节点编号为 1,2,…,n ，其中第 i 个节点的权值为 ai 定义一个连通块为"好连通块"：该连通块中所有节点的点权乘积尾数存在0 。
求好连通块的个数，结果对 109+7 取模。
对于树上的任意一个点集 S，如果点集中的仼意两点 u,v 满足" u 到 v 的简单路径上的所有点都在点集中"，则称 S 是一个连通块。特别地，单独的点也构成一个连通块。
输入描述
第一行输入一个整数 n(1≤n≤105) ，表示树的节点数。
第二行输入 n 个整数 a1,a2,…,an(1≤ai≤109) ，表示每个节点的权值。
接下来 n−1 行，每行输入两个整数 u 和 v ，表示树上的一条边 (u,v) 。
输出描述
输出一个整数，表示好连通块的个数，结果对 109+7 取模。
样例1
输入
3
2 5 10
1 2
1 3
输出
4
说明
连通块 {3} 是好连通块，a3=10 。
连通块 {1,2} 是好连通块，a1×a2=10 。
连通块 {1,3} 是好连通块，a1×a3=20 。
连通块 {1,2,3} 是好连通块，a1×a2×a3=100 。
总共 4 个。
