给定一棵有N 个节点和 (N – 1) 条边的树，其中节点的值从 1 到 N，根节点为 1。任务是确定给定树中是否存在恰好包含 K 的子树素数节点。

解决思路：

• 使用深度优先搜索（DFS）来遍历树，计算每个子树中的素数节点。检查计数是否与 K 相等，如果找到，则答案设置为 true
• 使用埃拉托斯特尼筛法来有效地识别素数。

什么是深度优先搜索（DFS）
深度优先搜索是一种用于遍历或搜索树或图数据结构的算法。该算法从根节点开始（在图的情况下选择某个任意节点作为根节点），并在回溯之前沿着每个分支尽可能远地探索。

图的深度优先遍历（或 DFS）类似于树的深度优先遍历。这里唯一的问题是，与树不同，图可能包含循环（一个节点可能被访问两次）。为了避免多次处理节点，请使用布尔访问数组。一张图可以有多个 DFS 遍历。

树遍历技术：
与只有一种逻辑方式来遍历它们的线性数据结构（数组、链表、队列、堆栈等）不同，树可以用不同的方式来遍历。 
树形数据结构可以通过以下方式遍历：

1. 深度优先搜索或 DFS[list=1]

分步算法：

• 为树创建一个邻接列表adj并初始化一个从 0 到 n 的素数列表素数，使用埃拉托斯特尼筛法将 0 和 1 标记为非素数。
• 定义一个 DFS 函数 (DFS(node, adj, prime, vis, ans, k))，将当前节点标记为已访问，计算其子树中的素节点数，如果计数等于 k，则递增 ans。
• 对当前节点的未访问邻居递归调用该函数。
• 初始化访问列表 vis 和答案列表 ans，并为根节点（例如节点 1）调用 DFS。
• 检查ans列表中的值是否大于0，如果大于则返回true，否则返回false。

C++代码：

include <bits/stdc++.h>
using namespace std;

// Function to start iterating from node 1
int dfs(int node, vector<vector<int> >& adj,
        vector<bool>& prime, vector<int>& vis, int& ans,
        int K)
{

    if (ans > 0)
        return 0;

    // If node is visited
    vis[node] = 1;

    int ele = 0;

    // 如果节点是质数
    if (prime[node])
        ele += 1;

    // 进一步迭代到其相邻节点
    for (auto j : adj[node]) {
        if (vis[j] == 0) {
            ele += dfs(j, adj, prime, vis, ans, K);
        }
    }

    //如果质数总数为 K
    if (ele == K) {
        ans += 1;
    }

    // Return ele
    return ele;
}

//查找树是否有
// K 素子集的函数
bool hasKPrimeSubtree(int N, int K,
                    vector<vector<int> >& edges)
{
    // 创建邻接矩阵
    vector<vector<int> > adj(N + 1, vector<int>());

    //边缘迭代
    for (auto j : edges) {

        int u = j[0];
        int v = j[1];
        adj.push_back(v);
        adj[v].push_back(u);
    }

    //创建质数向量
    vector<bool> prime(N + 1, 1);

    //因为 0 和 1 都不是质数
    prime[0] = prime[1] = false;

    //填充质数向量
    for (int p = 2; p * p <= N; ++p) {
        if (prime[p] == true) {
            for (int i = p * p; i <= N; i += p)
                prime = false;
        }
    }

    // 检查已访问元素的向量
    vector<int> vis(N + 1, 0);
    int ans = 0;

    // 开始在树中迭代的函数
    int ele = dfs(1, adj, prime, vis, ans, K);
    return (ans > 0);
}

// Driver code
int main()
{

    int N = 3;
    int K = 1;
    vector<vector<int> > edges = { { 1, 3 }, { 1, 2 } };

    // Function call
    cout << hasKPrimeSubtree(N, K, edges);
    return 0;
}

时间复杂度： O(N * log(log(N)))，其中N是树中的节点数。
辅助空间： O(N)