《<图上的游戏>命题报告》学习笔记

简要题意

这是一道交互题。

交互器有一个无自环的无向连通图 (G=(V={0,1,ldots,n-1},E={0,1,ldots,m-1}))。你需要通过如下询问来确定这张图：每次询问你可以给出 (Ssubset E,uin V)，交互器会返回在 (G'=(V,Esetminus S)) 中 (0) 和 (u) 是否联通。保证交互器不自适应。

(1leq n,mleq 600)，询问次数上线为 (3000)。

题解

前置算法

对于一个大小为 (n) 的集合(S)，其中有 (m) 个好元素。若每次可以选定 (Tsubset S)，询问 (T) 中是否有好元素。那么可以通过对 (S) 分治，在 (O(mlog n)) 次询问内找到所有好元素。

链的做法

按照随机顺序加入所有点，维护已加入点的相对顺序以及两两相邻点之间的边集。加入一个点时可以二分找到它的位置，然后暴力判断它插入的区间中的所有边在它的哪一侧。期望询问次数为 (O(nlog n))。

树的做法

不妨设该树以 (0) 为根。

考虑将树拆成若干条链。具体地，给每个非根结点一个颜色，使所有同色的点组成了树上的一条链。且满足每条链顶端的父亲所在的链的颜色比它小。设一条边的颜色为其较深的端点的颜色。

初始时所有点和边均无颜色。考虑依次加入所有点，维护已确定的所有边的颜色。不妨设此时加入的节点为 (u)：

若 (u) 可以被已确定颜色的边与根连通，则说明 (u) 的颜色已出现过。可以通过二分来确定 (u) 的具体颜色（每次保留颜色 (leq mid) 的边，判断 (u) 和根是否连通）。
否则，令 (u) 的颜色为一种新的颜色（比所有其他颜色都大）。接着确定所有这种颜色的边，注意到可以通过前置算法求出（一个无色边集 (S) 包含此类边，当且仅当保留 (Esetminus S) 时 (u) 和根无法联通）。

拆分成链后，链内部的边可以通过链的做法求出，于是只用求出每条链顶端的父亲。

考虑按照颜色从小到大确定所有链，每次可以通过二分 dfs 序来求出链顶的父亲（保留两个端点 dfs 序均 (leq mid) 的边，判断链顶和根是否连通），然后更新该链的 dfs 序。

询问次数 (O(nlog n))。

图的做法

考虑先找出一棵生成树。

考虑依次加入所有点，维护连通已加入点的生成树。加入节点 (u) 时，进行如下操作直到仅保留树边后 (u) 能与根连通：

依次删除每条非树边直到 (u) 不能与根连通，将最后被删的边加入树边，然后还原所有被删除的边。容易发现此做法可以通过二分前缀来优化询问次数。

确定了生成树之后树边可以通过树的做法求出，于是只用确定非树边。

考虑按 dfs 序倒序每次确定一个节点，然后将连向该点所有的边删除。不妨设此时的待确定节点为 (u)（不难发现此时 (u) 一定为叶子），可以通过前置算法求出连向 (u) 的所有非树边集合（一个非树边集 (S) 包含连向 (u) 的边，当且仅当保留 (S) 和除了 (u) 连向父亲的边之外的所有树边后 (u) 和根可以连通）。然后可以通过二分 dfs 序来确定每条边的另一个端点。