cf526D

无标签
ACM 老Blog迁移 reading_problem
发布日期:   2019-08-05
转移自老blog

cf526D

链接

题意

        给你一棵树，在树中找出一条路径（也可以只有一个点），让这条路径(点权和-边权和)最大。
        树的节点最多3e5，权值最大1e9

题解

        随便找个节点当根，dp1[i]代表以i为根的子树上，经过i点，走向子树的路径的最大权值，dp2[i]为次大。得到此数组之后，定义路径的深度节点为路径上的所有节点中，深度最小的那个节点，枚举每个节点作为深度节点的时候的最大权值路径，如果dp2<0则取dp1,否则取dp1+dp2转移
文章作者: fightinggg
文章链接: http://fightinggg.github.io/matery/matery/cf526D.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
无标签
赏
  目录