考虑一个合法图，每次删度数最小的点，删的时候与剩下部分相连都不超过 $k$ 条边 —— 这明确指向，我们可以通过这样的方式给图染色，将图分成 $k+1$ 个独立集。
于是，考虑增量。每次加入 $i$ 时，将 $[1,i-1]$ 划分独立集，然后每个独立集单独询问即可。因为独立集个数至多为 $k+1$，所以代价不超过 $nk+n(k+1)$ 。
QOJ.ac
QOJ
Discussion #1012 for Problem #4218. Hidden Graph
Type: Editorial
Status: Open
Posted by: Qiuly
Posted at: 2026-02-14 01:41:26
Last updated: 2026-02-14 01:41:30
题解
Comments
No comments yet.