考虑一个合法图，每次删度数最小的点，删的时候与剩下部分相连都不超过 $k$ 条边 —— 这明确指向，我们可以通过这样的方式给图染色，将图分成 $k+1$ 个独立集。
于是，考虑增量。每次加入 $i$ 时，将 $[1,i-1]$ 划分独立集，然后每个独立集单独询问即可。因为独立集个数至多为 $k+1$，所以代价不超过 $nk+n(k+1)$ 。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.