【题解】CF1651E

· · 题解

感觉大家的数数方式都和我不一样。

每个点度数为 2，说明整个图是由若干个偶环组成的，我们考虑从其中取两个区间，剩下来的图显然是若干个环和若干条链，所以我们对每个环和链统计贡献即可。

首先是环，我们记一个环长为 len 上左部点编号最大值，最小值为 lmax，lmin，右部点编号最大值，最小值为 rmax，rmin，显而易见，这个环对答案的贡献为 lmin(n - lmax + 1)rmin(n - rmax + 1)\dfrac{len}{2}。

其次是链，我们枚举所有的链，共 O(n^2) 条，然后同上记下链上的这四个信息，但是这条链对答案能造成贡献，还要考虑这条链左右两侧的点会不会被选中，再记录一下链外两点的信息即可。

时间复杂度 O(n^2)。Code