题面 [Luogu P4768] [NOI2018]归程 Solution 这题可能要用到Kruskal重构树的相关知识，如果有需求的同学可以看这里 首先，根据我们之前在运输计划那道题的经验，我们会发现我们开车能经过的边一定在以海拔为关键字的最大生成树上。 根据Kruskal重构树的性质：Kruskal重构树是一个堆，我们可以考虑这样做： 我们先把Kruskal重构树按每条路的海拔从大到小...

题面 传送门：洛谷 Solution 如果题目只要求求出第一问，那这题显然就是大水题。 但是加上第二问的话…那这题就成为大（du）火（liu）题了。 对于第一问：求一整个区间的最大线段总数，我们可以很轻松的切掉。 怎么处理第二问呢？ 我们可以考虑这样做： 对于一条线段，如果它属于答案的一部分，那么它一定会有以下性质： 区间③的最大线段数 = 区间①的最大线段数 + 区间②的最大线段数 + ...