自然公园 / Natural Park JOISC 2017

[JOISC 2017] 自然公园 / Natural Park

NOIPlus 模拟赛 T4 放这个……

题目链接： [JOISC 2017] 自然公园 / Natural Park 。

题目描述：

有一个未知的 $n$ 个点 $m$ 个边的无向连通图，点编号 $0$ 到 $n-1$ 。

每次你可以调用 Ask(A,B,Place[]) 来询问只经过 $Place[]$ 中的点时是否能从 $A$ 到 $B$ 。需满足 $A$ 和 $B$ 在点集中且 $A<B$ 。 $Place[]$ 是一个数组， $Place[i]=1$ 表示可以经过 $i$ ， $Place[i]=0$ 表示不可以经过 $i$ 。

Ask 操作调用次数不能超过 $45000$ 次。

你需要还原出这个无向连通图的每一个边，你可以调用 Answer(A,B) 来报告一条边，需满足 $A<B$ 。

你需要实现函数 Detect(int T,int n) 完成以上任务。

交互库不是自适应的。

特别的：

• 当你答案正确时，交互库返回 Accepted ，否则返回 Wrong Answer[wa_num] 。
• 当你调用 Answer 且不满足 $0\le A<B<n$ 时，返回 Wrong Answer[1] 。
• 当你调用 Answer 且不满足原图中有 $A$ 和 $B$ 的边时，返回 Wrong Answer[2] 。
• 当你调用 Answer 且 Answer(A,B) 在相同参数的情况下被调用超过一次时，返回 Wrong Answer[3] 。
• 当你调用 Ask 且不满足 $0\le A<B<n$ 或 $Place[A]=0\ \lor Place[B]=1$ 或 $\exists i,\ Place[i]\notin\{0,1\}$ 时，返回 Wrong Answer[4] 。
• 当你调用 Ask 次数超过 $45000$ 时，返回 Wrong Answer[5] 。
• 当你调用 Detect 结束后你 Answer 的边数少于 $m$ 条时，返回 Wrong Answer[6] 。
• 当你满足多种错误时，交互库会返回任意一个。

子任务：

• Sub1 $10\%$ ： $n\le250$ 。
• Sub2 $10\%$ ： $m=n-1$ 且树为一条链且 $0$ 和 $n-1$ 为链的两端。
• Sub3 $30\%$ ： $m=n-1$ 且树以 $0$ 为根时高度不超过 $10$ 。
• Sub4 $20\%$ ： $m=n-1$ 。
• Sub5 $30\%$ ：无。

对于所有数据，满足无重边自环， $n\le1400,m\le1500$ ，且每个点度数不超过 $7$ 。

警示后人：

调用 Ask 时要满足 $A<B$ ，模拟赛没看到失去了 Sub2 $10$ 分。

Sub1 很简单，暴力判断就行。 Sub2 使用类似快速排序的方法，每次随机一个点后可以 $O(n)$ 次操作得到端点到这个点上的所有点，然后递归的判断就行。

以上是考场分析，跟正解没有任何关系。

考虑 Sub2 的一个可扩展的想法：假设我已经得到了链的一部分，然后我可以随机一个点 $x$ 并 $O(1)$ 次询问得到他在链的哪一边。然后只需要知道这一边的端点和 $x$ 的边就行。此时可以二分出一个最小的 $mid$ 使得只经过点编号 $[1,mid]$ 内的点可以使端点和 $x$ 联通。那么显然 $mid$ 为端点到 $x$ 路径上编号最大的点。那么此时可以递归的判断端点到 $mid$ 和 $mid$ 到 $x$ ，边界条件为端点和 $x$ 有连边。这个也是类似于快速排序的想法，不过我的那个随机一个点只能做链，而这个可以扩展。因为只有链的情况能保证随机一个点一定在路径上。

然后是 Sub4 ，跟上面一样的想法，假设我已经得到了树的联通子树，然后我可以随机一个点 $x$ ，同样的得到一个类似于链接 $x$ 和联通子树的那个端点，然后就变成了和 Sub2 一样的处理。所以问题在于如何求出链接 $x$ 和联通子树的端点。不妨给树打一个 dfn ，那么我们可以二分一个最小的 $mid$ 使得只保留 dfn 在 $[1,mid]$ 内的点和所有不在联通子树内的点时联通子树的根（因为他的 dfn 最小，可以钦定 $0$ 为根）和 $x$ 联通，那么此时可以得到一旦 $mid$ 缩小 $1$ 都会导致不连通，结合 dfn 的性质可以得到 $mid$ 就是我们要求的那个端点。这样 Sub4 就做完了。

最后是把 Sub4 的树做法扩展到图上。一样的我们需要得到随机一个 $x$ 并找到 $x$ 和联通子图路径上所有点和边。那么第一步也一样的是找到链接 $x$ 和联通子图的端点，这样的点有很多个，随便一个就行。找这个点的方法可以套用 Sub4 的方法，一样的。然后我们还需要找到路径上的点和路径上的点加入联通子图后的新产生的边。

先看如何找路径上的点。原先的方法变得不适用了。因为原先的方法可能会找到一个经过了联通子图内其他点的路径，这是不合法的。所以我们应该把 Sub2 的方法修改一下：二分一个编号最小的 $mid$ 使得只保留编号在 $[1,mid]$ 内的不在联通子图的点时满足端点和 $x$ 联通。然后像 Sub2 一样递归的找就行。

最后一步就是找到新的点与联通子图的点新产生的边。由于新的点和新的点以及新的点和原来的点都会有贡献，于是不妨增量的找边。每次按照路径上点的顺序加入一个点，找出他与联通子图的边后把他加入联通子图。不妨设当前要加入的点为 $x$ ，那么我们可以使用找端点时一样的方法找到一个链接联通子图和 $x$ 的端点 $mid$ ，那么由于我们增量顺序是按照路径的顺序，也就是说此时找到的 $mid$ 一定和 $x$ 有直接连边。但问题是 $x$ 可能不止和 $mid$ 有连边，也有可能和联通子图的其他点有连边。此时可以短暂的在联通子图中删掉这个 $mid$ 后，递归的让裂开的各个部分的联通子图与 $x$ 递归的使用和上面一样的方法就行，边界条件是 $x$ 个联通子图没有直接连边。

然后就做完了，代码十分好写，没有任何细节，不放了。