#P1618. 2023.10.07-MT-第五题-塔子哥的美好节点

2023.10.07-MT-第五题-塔子哥的美好节点

题目描述

塔子哥现在对树非常感兴趣，他定义树上的一个美好节点为，当他的子树的所有节点的乘积至少有k个因子。塔子哥想知道这样的节点的个数是多少。树根是 11 号节点。

输入描述

第一行输入两个整数n,kn,k。表示节点数量和至少需要的因子个数(1≤n≤105,1≤k≤1014)(1 \leq n \leq 10^5, 1 \leq k \leq 10^{14})。

第二行n个整数aia_i，表示节点值(1≤ai≤100)(1 \leq a_i \leq 100)。

接下来n−1n-1行，每行两个整数u,vu,v，表示u，v之间有一条边。

输出描述

一个整数，表示有美好节点的个数。

样例

输入

3 3
1 2 3
1 2
2 3

输出

2

说明

第一个节点子树节点乘积为6，有4个因子，符合要求

第二个节点子树节点乘积也为6，同样符合要求

第三个节点子树节点乘积为3，有2个因子，不符合要求

知识点:*****

查看知识点以及同类型题目

Statistics