题目理解

我们有一个 $N$ 个节点的连通无向图，需要找出两个特殊节点 $A$（钥匙）和 $B$（宝箱）。通过设置每条边的方向并查询从 $A$ 到 $B$ 是否可达，最多进行 300 次查询。

关键观察

1. 问题转化

将无向图通过设置边方向转化为有向图，通过可达性查询来推断 $A$ 和 $B$ 的位置。

2. 核心思路

利用拓扑排序和二分查找的思想：

• 如果能找到一个节点的排列（拓扑序），使得 $A$ 在 $B$ 前面，那么存在从 $A$ 到 $B$ 的路径
• 通过精心构造的边方向设置，可以推断出 $A$ 和 $B$ 的相对位置

算法核心

树分治 + 分层构造

代码使用了树分治的策略来构建多个有向图层次：

步骤1：构建生成树

void build() {
    // 从节点1开始DFS构建生成树
    // 标记树边 ont[id] = 1
}

步骤2：树分治

void solve(int u, int d) {
    // 找到重心rt
    // 将子树按边数分成两部分
    // 为两部分分别设置相反的方向
    // 递归处理两个子树
}

步骤3：构建分层图

对于分治的每一层 $d$，构建两个有向图：

• gr[2*d-1]: 一部分边从浅到深
• gr[2*d]: 另一部分边从深到浅

这样确保在某一层中，$A$ 和 $B$ 的相对位置会被正确捕获。

步骤4：查询处理

for d = 1 to mxd:
    if gr[d].query():  // 在该层图中A能到达B
        // 使用二分查找精确定位A和B

精确定位算法

查找A（钥匙）：

int L = 1, R = n + 1;
while L + 1 < R:
    mid = (L+R)/2
    // 设置边方向：前mid个节点按拓扑序，后面的反向
    if query(vec): L = mid  // A在前mid个中
    else: R = mid
a = perm[L-1]

查找B（宝箱）：

int L = 0, R = n;
while L + 1 < R:
    mid = (L+R)/2  
    // 设置边方向：后mid个节点按拓扑序，前面的反向
    if query(vec): R = mid  // B在后mid个中
    else: L = mid
b = perm[R-1]

算法正确性

1. 分治策略

通过树分治，确保每个节点对 $(A,B)$ 在某一层分治中会被分到不同的子树，从而它们的相对位置会被正确设置。

2. 方向设置

在分治的每一层，将边分成两组并设置相反的方向：

• 一组：从父节点指向子节点
• 另一组：从子节点指向父节点

这样确保了拓扑序的一致性。

3. 二分定位

通过二分查找在拓扑序中精确定位 $A$ 和 $B$：

• 找 $A$：固定后半部分的反向，二分前半部分
• 找 $B$：固定前半部分的反向，二分后半部分

时间复杂度

查询次数分析

• 分治层数: $O(\log n)$
• 每层1次查询: $O(\log n)$
• 二分定位: $O(\log n)$ 次查询
• 总查询次数: $O(\log n)$

在 $N \leq 10000$ 时，$\log n \approx 14$，远小于 300 的限制。

算法优势

1. 分层处理: 通过树分治将问题分解
2. 方向对称: 每组边设置相反方向，确保捕获所有相对位置
3. 二分优化: 使用二分查找快速定位
4. 查询高效: 总查询次数为对数级别

关键数据结构

1. 图存储: G[kMaxN] 存储原图
2. 生成树: T[kMaxN] 存储DFS生成树
3. 分层有向图: gr[100] 存储分治各层的有向图
4. 分治信息: sz[], mx[], del[] 用于树分治

算法标签

• 树分治
• 拓扑排序
• 二分查找
• 图论

总结

该算法通过巧妙的树分治策略，将复杂的图论交互问题转化为分层的有向图可达性问题。通过构建多个互补的有向图层次，确保能够捕获钥匙和宝箱的所有可能相对位置。最后通过二分查找在拓扑序中精确定位，实现了高效的问题求解。算法设计精妙，查询次数优化到对数级别，是该类交互问题的典范解法。