交互题

1. LOJ2398. 「JOISC 2017 Day 3」自然公园

有一棵树，需要通过至多45000次Ask操作确定这棵树的形态。

Ask(x,y,P)表示只通过集合P中的点x和y是否连通。

每个点的度数至多为7。

n≤1400

general idea

维护一个连通块，和其一个生成树的拓扑序。通过二分找到一个与连通块直接相连的点，在二分找到那些的与其相连。

difficulty

2. LOJ6736. 「2020 集训队论文」最小连通块

给定一棵树 T，我们定义这棵树上的某个点集S的最小连通块为包含这个点集中所有点的最小的树上连通块。

给定一棵树的大小n，你可以进行若干次询问，每次询问你可以给出一个点集S和这棵树上的一个点x，交互库会返回一个布尔值 表示x是否在点集S的最小连通块上。你需要确定这棵树的形态。

general idea

一个个加点，维护其虚树的拓扑序。
在从后往前二分找儿子。

difficulty

3. LOJ3031. 「JOISC 2019 Day1」聚会

给一棵树，询问一个点为根时，另外两点lca。
度数<=18

general idea

如果是一条链，那么一次询问可以知道两个点的相对顺序。
由于度数限制，可以随机两个点，找到路径上的点，并递归到子树中。
若无度数限制：？

difficulty

4. 自己yy的题

给一棵树，询问一个点集形成的连通块个数。

general idea

通过询问，和，可以知道x是否和有边，在线段树上二分即可得到所有边。

difficulty