济南诚一化工有限公司

  • 电话:15063337358
  • 传真:0531-85932887

牛客练习赛40题解

作者:wellbet-wellbet手机官方网站-吉祥体育手机官网 发布时间:2020-07-02 18:11:29

  以完成时间为关键字从小到大排序(可以交换两个完成时间不同的任务来证明这样的正确性),按这个顺序来做任务,同时维护一个关于最大的任务来花费金币,维护每个任务的剩余时间,如果花费金币后剩余时间不为 0 则重新push入堆

  先考虑回路的情况。由于是一棵树,任两点间路径只有一条,从一条边走到深度更大的点,一定还会从同一条边返回以回到起点或者遍历其他子树,所以每条边需要复制一次,此时答案是边权和的两倍。

  不是回路的情况可以减掉从终点回到起点的路径,要让这条路径尽量长,所以长度一定是直径的长度。