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