思路：树形DP+数论

给定一个数字$x$

它的因子个数为对他进行质因数分解后得到的所有质数，每个质数出现的个数+1累成的结果

例如15的因子个数就是4，它有两个质数，3和5，各出现了因此，因此因子个数为$(1+1)\times (1+1)=4$

因此，对于以$i$为根节点的子树的所有节点乘积的因子个数

我们可以分别统计以$i$为节点各个质数出现的次数，然后就可以变乘法为加法，把所得结果累加即可

因为100以内的质数只有20个左右，因此整体的时间复杂度仅为$O(20n)$，不会超时。

时间复杂度

$O(20n)$

代码

C++

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
vector<vector<int>> sum(N,vector<int>(101,0));
void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<int> val(n);
    for(int i = 0;i < n;i++) {
        cin >> val[i];
    }
    vector<vector<int>> g(n,vector<int>());
    for(int i = 0;i < n - 1;i++) {
        int u,v;
        cin >> u >> v;
        u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 0;i < n;i++) {
        int v = val[i];
        for(int j = 2;j <= v;j++) {
            if(v % j == 0) {
                while(v % j == 0) {
                    sum[i][j]++;
                    v /= j;
                }
            }
        }
    }
    auto dfs = [&](auto self,int cur,int f) -> void {
        for(int next : g[cur]) {
            if(next == f) continue;
            self(self,next,cur);
            for(int j = 2;j <= 100;j++) {
                sum[cur][j] += sum[next][j];
            }
        }
    };
    dfs(dfs,0,-1);
    int ans = 0;
    for(int i = 0;i < n;i++) {
        ll cur = 1;
        for(int j = 2;j <= 100;j++) {
            if(sum[i][j] > 0) {
                cur *= (1 + sum[i][j]);
                if(cur >= k) break;
            }
        }
        if(cur >= k) ans++;
    }
    cout << ans << endl;
}
int main() {
    solve();
}

python代码

import sys
sys.setrecursionlimit(100000)

n, k = map(int, input().split())
v = [0] + list(map(int, input().split()))
e = [[] for i in range(n+1)]
for i in range(n-1):
    x, y = map(int, input().split())
    e[x].append(y)
    e[y].append(x)
p = []
for i in range(2, 100):
    p.append(i)
    for j in range(2, i):
        if i % j == 0:
            p.pop()
            break
m = len(p)
cnt = [[0]*m for i in range(n+1)]
for i in range(1, n+1):
    for j in range(m):
        while v[i] % p[j] == 0:
            v[i] //= p[j]
            cnt[i][j] += 1
def dfs(s, fa):
    res = 0
    for to in e[s]:
        if to == fa:continue
        res += dfs(to, s)
        for i in range(m):
            cnt[s][i] += cnt[to][i]
    sum = 1
    for i in range(m):
        sum *= cnt[s][i] + 1
        if sum >= k:
            res += 1
            break
    return res
print(dfs(1, 0))

Java代码

import java.util.*;
import java.io.*;
import java.util.StringTokenizer;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    static List<Integer>[] son;
    static int res = 0, n, k;
    static List<Integer> prime;
    static int[] val;
    static boolean[] vis;

    static int[] dfs(int root) {
        int[] ret = new int[prime.size()];
        vis[root] = true;
        int num = val[root];
        for (int i = 0; i < ret.length; i++) {
            while (num % prime.get(i) == 0) {
                num /= prime.get(i);
                ret[i]++;
            }
        }
        for (int j : son[root]) {
            if (!vis[j]) {
                int[] tmp = dfs(j);
                for (int k = 0; k < ret.length; k++) {
                    ret[k] += tmp[k];
                }
            }
        }
        long m = 1;
        for (int i = 0; i < ret.length; i++) {
            m *= (ret[i] + 1);
            if (m >= k) {
                res++;
                break;
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        prime = new ArrayList<>();
        for (int i = 2; i <= 100; i++) {
            boolean f = true;
            for (int j : prime) {
                if (i % j == 0) {
                    f = false;
                    break;
                }
            }
            if (f) {
                prime.add(i);
            }
        }
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        n = in.nextInt();
        k = in.nextInt();
        val = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            val[i] = in.nextInt();
        }
        son = new List[n + 1];
        for (int i = 0; i < son.length; i++) {
            son[i] = new ArrayList<>();
        }
        for (int i = 0; i < n - 1; i++) {
            int a = in.nextInt(), b = in.nextInt();
            son[a].add(b);
            son[b].add(a);
        }
        vis = new boolean[n + 1];
        dfs(1);
        System.out.println(res);
    }
}

// 注意类名必须为Main
class FastReader {
    StringTokenizer st;
    BufferedReader br;

    public FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    String nextLine() {
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }

}

题目描述

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

输入描述

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

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

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

输出描述

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

样例

输入

3 3
1 2 3
1 2
2 3

输出

2

说明

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

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

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