题目大意
题目总结：H. Hybrid Search（混合搜索）
问题描述
给定一棵以 为根、包含 个节点的树。对于树上的特定目标节点 ，你需要计算在以下两种“混合搜索”策略下， 被访问到的最小可能位置（从 开始计数）：
-
策略 A (BFS DFS)：从根节点开始进行 广度优先搜索 (BFS)，在某一节点 处切换为 深度优先搜索 (DFS)。切换后，搜索将仅限于 的子树内部。
-
策略 B (DFS BFS)：从根节点开始进行 深度优先搜索 (DFS)，在某一节点 处切换为 广度优先搜索 (BFS)。切换后，搜索将仅限于 的子树内部。
规则说明
-
*切换点 **：可以是路径上的任意节点（包括根节点 或节点 本身）。切换时 必须已被第一阶段搜索访问。
-
搜索范围限制：一旦切换搜索类型，后续只能访问 的子树节点。这意味着为了能访问到 ，切换点 必须是 的祖先（或 本身）。
-
邻居访问顺序：在任何搜索中，节点子树的访问顺序严格遵循输入中边出现的先后顺序。
-
计算目标：分别输出在策略 A 和策略 B 下，节点 可能出现的最小位次。
样例解释
样例 1 ()
-
BFS DFS：最优选择是在节点 处切换。BFS 首先访问第一层及第二层部分节点，到达 后切换为 DFS 进入其子树，此时 是第 个被访问的节点。
-
DFS BFS：最优选择是在节点 或 处切换，最小位次为 。
样例 2 ()
-
BFS DFS：最小位次为 。
-
DFS BFS：即使不切换（一直使用 DFS），最小位次也可以达到 。
样例 3 ()
- 无论哪种混合搜索，最优答案均为 。注意，如果仅使用纯 BFS 或纯 DFS，节点 的位次都是 。混合搜索通过在特定节点（如 的祖先）切换策略，跳过了其他非必要的分支，从而提前了 的访问顺序。
输入输出要求
-
输入：第一行 ；接下来 行描述边。
-
输出：第一行输出策略 A 的最小值，第二行输出策略 B 的最小值。
-
数据范围：。
思路讲解
AC代码
源代码
1 |