难得做出了 3400 的构造,很有意思的题目.
从小到大考虑每个好区间.
对于长度为 $d$ 的好区间 $[lr]$,此时所有长度 $<d$ 的好区间都已经满足题意,首先由于我们的构造方式,所有的连通块都是区间.假如 $lr$ 处于不同的连通块,我们会连一条 $l\to r$ 的边将两个连通块合并,注意此时在 $lr$ 所在的连通块之间还可能存在一些散块,我断言散块的数量不可能为 $1$,否则显然无解,既然散块的数量大于 $1$,容易想到构造左往右连,右往左连这样的交叉连边,这样如果不同时包含 $lr$,任取若干散块,他们仍然不连通,于是就保证了不会破坏较小区间的正确性.
实现细节略去,代码十分易懂.
值得一提的是,枚举所有好区间的复杂度是 $\mathcal O(n^2)$,而对于每个尚未连通的好区间,我们都暴力遍历了区间中的每个点检查连通性,尽管如此,由于每次暴力遍历都至少会连一条边,而树上的总边数是 $n-1$,故总复杂度是正确的 $\mathcal O(n^2)$.
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可.