题解：Tree Search 解题思路与实现

问题分析

本题要求在一棵有根二叉树中，通过最多 $35$ 次询问找到找到特殊顶点。每次询问可判断特殊顶点是否在某个顶点的子树中，需设计高效的查询策略。

核心思路：重心分解法

利用树的重心特性进行二分查找，每次将搜索范围缩小一半，确保在对数级询问次数内找到目标。

1. 树的重心定义：树中某个顶点，删除该顶点后，剩余各子树的大小均不超过原树大小的一半。
2. 查找逻辑：
   • 从根节点开始，找到当前子树的重心
   • 询问重心是否包含特殊顶点
   • 若不包含（返回 $0$），则排除重心及其子树，在剩余部分继续查找
   • 若包含（返回 $1$），则在重心的子树内继续查找
   • 重复上述过程，直到找到唯一顶点（叶子节点）

代码实现解析

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

const int N = 100005;
vector<int> t[N];  // 存储树的邻接表
bool used[N];      // 标记已排除的节点

int pos, v, siz[N], sum, n;

// 计算子树大小并寻找当前子树的重心
void dfs(int x) {
    siz[x] = 1;  // 初始化为1（包含自身）
    for (int i : t[x]) {
        if (used[i]) continue;  // 跳过已排除的节点
        dfs(i);
        siz[x] += siz[i];       // 累加子树大小
    }
    // 计算以x为重心时的最大子树大小
    int val = max(siz[x], sum - siz[x]);
    // 更新重心（选择最大子树最小的节点）
    if (val < v) {
        v = val;
        pos = x;
    }
}

// 递归查找特殊顶点
int work(int rt, int s) {
    sum = s;       // 当前子树总大小
    v = 1e9;       // 初始化最大子树大小的最小值
    dfs(rt);       // 寻找当前子树的重心

    if (siz[rt] == 1) return rt;  // 找到唯一节点，返回结果

    bool res = ask(pos);  // 询问重心是否包含特殊顶点
    if (res == 0) {
        // 不包含，排除重心及其子树，在剩余部分继续查找
        used[pos] = true;
        return work(rt, s - siz[pos]);
    } else {
        // 包含，在重心的子树内继续查找
        return work(pos, siz[pos]);
    }
}

// 主函数：初始化树结构并启动查找
int solve(int _n, std::vector<int> p) {
    n = _n;
    // 构建树的邻接表（p[i]是i+2的父节点）
    for (int i = 0; i <= n - 2; ++i) {
        t[p[i]].push_back(i + 2);
    }
    // 从根节点（1）开始，初始总大小为n
    return work(1, n);
}

复杂度分析

• 时间复杂度：每次查找重心的 $DFS$ 复杂度为 $O(k)$（$k$ 为当前子树大小），总复杂度为 $O(N \log N)$，符合 $N \leq 10^5$ 的限制。
• 询问次数：每次将问题规模缩小至少一半，最多需要 $\log_2(10^5) \approx 17$ 次询问，远低于 $35$ 次的限制，满足题目要求。

关键优化

通过标记已排除的节点（used 数组），避免重复处理无关子树，确保每次 $DFS$ 仅遍历当前有效范围，提高效率。

该方法利用树的重心特性实现高效二分，是解决此类查找问题的经典思路，适用于各种树结构（不仅限于二叉树）。