CFgym102759E Chemistry 发表于 2025-02-22 更新于 2025-02-27 分类于 算法竞赛 ， 题 ， Codeforces 阅读次数： XXI Open Cup, Grand Prix of Korea 题意：给出一张 个点 条边的无向图。 求有多少个区间点集 的导出子图为一条链（不一定要以标号为序）。 ，时限 。 某个点集的导出子图是一条链的充要条件： 没有环 边数等于点数减一（达到上界） 没有三度点 从左到右枚举右端点，考虑每个左端点对应的区间是否合法。 无环：用 LCT + 双指针维护。这会去掉一个前缀。 无三度点：维护每个点的度数，双指针。这也会去掉一个前缀。 边数等于点数减一 ： 对于位置 ，记 表示点集 的导出子图的边数。 若新加一条边 ，则将 加一。 最终我们要询问有多少 的位置，只需用线段树维护 ，然后区间查询最大值与最大值个数即可。 复杂度 。