考虑三角剖分对应的弧。
删,加边使得三角剖分的所有边都有公共端点,设这个公共端点为 \(x\)。我们令所有边对应的弧都是不经过 \(x\) 的弧。要使在删除过程中保持三角剖分,则:
-
两条弧的关系要么是相交,要么是包含。
-
每次删除的边对应的弧都是极大的,即不被任何弧包含。
-
最小次数为 \(n - 3 - cnt\),其中 \(cnt\) 为 \(x\) 端点的弧。
于是我们可以将删边的操作看做对森林的拓扑排序,方案数为 \(\frac{n}{\prod sz_i}\)。
考虑原本的弧为 \((l, r)\),则其子树的大小为 \(r - l - 1\)。然后随便维护即可。
感觉像是 P10230 的口胡,不管了。