【题解】P8984 [北大集训 2021] 末日魔法少女计划

https://www.luogu.com.cn/problem/P8984

把题意变成人话。
构造一个 DAG，满足：

• 只存在 \(u<v\) 的 \(u\to v\) 边。
• 对于所有 \(i\) 都存在 \(i\to i+1\) 的边。
• 对于所有边 \((u,v)\)，要么 \(u+1=v\)，要么存在 \(u\to t\to v\)。
• 任意点对在走不超过 \(k\) 条边后可达。

要求最小化边数 \(+n\)。