冬令营前交互专练
P13782 [eJOI 2022] Where Is the Root?
有点唐。发现交互次数是严格 \(\log n\)，启发我们想到二分答案。我们做一些基本的分类讨论：
- 假设根节点不为叶子节点，如果我们每次都询问所有叶子节点，那么只有在询问集合中有根节点的时候才会回答
YES。 - 假设根节点为叶子节点，如果我们逐个加入每个叶子节点，那么只有在询问集合中有根节点的时候才会回答
YES。
结合上面的两个分析，我们可以得出一个做法：将所有点按照度数排序，然后二分答案，check 的方式是询问 \(1\sim mid\) 中所有点，看回答是不是 YES，如果是说明根节点在 \([l,mid]\)，否则在 \((mid,r]\)。注意到此时如果 \(mid=1\) 会有问题，但是题目中保证了至少有三个叶子，所以我们问一下第一个点和第三个点即可。这样的话我们的操作次数是严格 \(\log n\) 的，可以通过。