先观察问题，因为这个问题中阶段性工作完成代表的是最慢的运输结束，所以这个问题实际上是让最大的时间最小的问题 最大的最小，这一类问题有一个统计上显著有效的方法是二分答案 考虑二分答案，问题变为怎么检查是否能让所有运输计划的时间都<=x 那么，如果有一个运输计划的时间<=x，那我们不需要考虑其，因为将一条边变成虫洞只可能让时间变短 如果有一个运输计划的时间>x，则我们选择的虫洞必须为这个运输计划上的一条边，否则这个运输计划的时间不会缩短 即问题转换为求一条边，使得其在一些路径的交上，这条边边权变为0后所有这些路径是否<=x 假设路径的交为空，那答案一定是不行 否则，我们可以贪心地选择一条边权最大的路径交中的边变为0 怎么求路径的交呢？ 我们将每条路径看做是一个树上的链+1，当所有+1操作结束后，我们检查树上每条边的边权 如果边权为路径条数，则这条边在交集里 这部分时间复杂度O(n+m) 我们可以先预处理出每个运输计划的lca，这样就不用每次检查的时候求lca了，因为求lca挺慢的 于是总时间复杂度O((n+m)logn) 这题比较卡常，当年NOIP只有几个满分的人就是因为这题卡常，有一个重要的常数优化方法： DFS是非常慢的东西，这道题可以先处理出树的拓扑序，然后for拓扑序即可，大家做题的时候尽量不要在瓶颈的地方使用DFS，常数是非常大的