恰好有K个素数的子树
内容提要
给定一棵有N个节点和(N-1)条边的树，判断是否存在恰好包含K的子树素数节点。使用DFS遍历树，计算每个子树中的素数节点。使用埃拉托斯特尼筛法识别素数。时间复杂度O(N * log(log(N)))，辅助空间O(N)。
延伸解读
算法核心：DFS与素数筛法的结合
文章通过深度优先搜索（DFS）遍历树，同时利用埃拉托斯特尼筛法预先标记素数节点。DFS在回溯时累计子树中的素数数量，并与目标K比较。这种方法将树遍历与素数识别分离，筛法预处理确保素数判断为O(1)，整体效率较高。
时间复杂度分析：为何是O(N log log N)
埃拉托斯特尼筛法预处理素数的时间为O(N log log N)，DFS遍历每个节点一次，邻接表遍历所有边，总时间为O(N)。因此整体时间复杂度为O(N log log N)，主要由筛法决定。辅助空间包括邻接表、素数标记和访问数组，均为O(N)。
实现细节与潜在问题
代码中邻接表的构建存在错误：`adj.push_back(v)` 应为 `adj[u].push_back(v)`，否则会导致邻接表错误。此外，素数筛法内层循环中 `prime = false` 应为 `prime[i] = false`。这些笔误可能影响程序正确性，读者需注意修正。
适用场景与扩展思考
该算法适用于静态树结构，且节点值固定为1到N。若节点值范围更大，筛法需调整上限。问题要求判断是否存在，而非计数，因此找到第一个满足条件的子树即可提前终止，但代码中通过ans累加并检查，未做提前退出优化。
Q&A
如何判断一棵树中是否存在恰好包含K个素数节点的子树？
使用深度优先搜索（DFS）遍历树，计算每个子树中的素数节点数量，并检查是否有子树的素数节点数恰好等于K。
为什么在解决这个问题时要使用埃拉托斯特尼筛法？
埃拉托斯特尼筛法可以高效地识别出1到N范围内的所有素数，为后续统计子树中的素数节点提供基础。
深度优先搜索（DFS）在这个问题中是如何工作的？
DFS从根节点开始递归遍历每个子树，统计当前子树中的素数节点数量，并在回溯时返回该数量，同时检查是否等于K。
解决这个问题的算法时间复杂度是多少？
时间复杂度为O(N * log(log(N)))，其中N是树中的节点数。
算法需要多少辅助空间？
辅助空间为O(N)，用于存储邻接表、访问标记、素数标记等。
能否提供解决这个问题的C++代码示例？
可以，代码包括创建邻接表、初始化素数筛、定义DFS函数递归统计素数节点，并最终判断是否存在满足条件的子树。
