本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-02 18:18:05

第一道自己想出做法的 CF Div.1 F，记录一下它的两种维护方式。

问题转化

$n$ 个点，每个点的度数最多是 $4$。
求有多少个点对 $(l,r)$ 满足 $1 \le l \le r \le n$，使得 $[l,r]$ 中的点构成的导出子图是一棵树。

考虑合法条件。

1. 不能存在环。
2. 边数等于点数减一。

考虑编号升序枚举右端点，想一想哪些左端点是符合要求的。

• 仅考虑条件一
  注意到，如果 $[l,r]$ 合法，那么 $r \ge \forall l' \gt l$，$[l',r]$ 是合法的。在右端点递增的情况下，最小的符合要求的左端点是单调不降的。
  基于此性质，可以双指针。右端每新增一个点，就需要从左端弹出若干个点，使得加上新的边后不会形成环，此过程可以 LCT 维护。
  整体二分同样可以完成任务。
  至此，求出了每个右端点对应哪些符合条件一的左端点。
• 考虑条件二
  考虑对每个点维护一个权值，代表其作为左端点时，总点数减去边数是多少。
  枚举右端点的时候使用线段树动态更新就可以。 注意到对于符合条件一的左端点，其权值必然大于等于 $1$，问题可以转化为求最小值及其出现次数。

虽然 LCT 常数巨大，但是在这道题可以吊打普通的整体二分。

其中 LCT 维护的时间复杂度是 $O(nm \log nm)$，整体二分多一个并查集的复杂度。

LCT submission，整体二分 submission。