原题等价于问竞赛图缩点后第一个强连通分量的点集,个人思路是先问一遍所有点的出度,按出度排序后找到最大的 ddd,若有 kkk 个点 di≥dd_i\ge ddi≥d,则满足 ∑di≥ddi−(n−k)=(k2)\sum_{d_i\ge d}d_i-(n-k)=\binom k2∑di≥ddi−(n−k)=(2k),然后这 kkk 个点就是答案。
感觉后 nnn 次询问完全没用上,而且做法挺玄乎的。问问能否 hack 或证明。
先睡了,醒了再看回复。