#P2956. 第3题-好联通块

    ID: 2591 Tried: 14 Accepted: 2 Difficulty: 10 所属公司 : 阿里 时间 :2025年5月12日-阿里国际(开发岗)
      算法标签>树形dp

第3题-好联通块

题目内容

小红获得一棵节点数为 nn 的树,节点编号为 1,2,,n1,2,…,n ,其中第 ii 个节点的权值为 aia_i 定义一个连通块为"好连通块":该连通块中所有节点的点权乘积尾数存在00

求好连通块的个数,结果对 109+710^9 + 7 取模。

对于树上的任意一个点集 SS,如果点集中的仼意两点 u,vu,v 满足" uuvv简单路径上的所有点都在点集中",则称 SS 是一个连通块。特别地,单独的点也构成一个连通块。