oxx1108 edited 4 年，11 月前
问题：
交互题，给一棵有根树 / DAG，需要找到一个目标结点 t。每次可以 query 一个结点 q，系统会返回是否存在一条 path 从 q 到 t。
链的时候直接二分就行。
树的时候树剖之后链上二分，对于儿子来说优先 query 结点个数总和多的子树。
DAG 上提取出 heavy DFS tree（按重边顺序DFS），在上面可以和 tree 一样做。（可以证明正确性，这个是唯一精妙的地方）
Research ideas:
For k targets?
Limit the number of query?
Problem ideas:
1. 每次返回目标点到查询结点的距离
2. 每次返回目标点是否在查询点的 k 步范围内