cf526D 2019-08-05 ACM老Blog迁移reading_problem nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 转移自老blog cf526D 链接 https://codeforces.com/contest/1084/problem/D 题意 给你一棵树,在树中找出一条路径(也可以只有一个点),让这条路径(点权和-边权和)最大。 树的节点最多3e5,权值最大1e9 题解 随便找个节点当根,dp1[i]代表以i为根的子树上,经过i点,走向子树的路径的最大权值,dp2[i]为次大。得到此数组之后,定义路径的深度节点为路径上的所有节点中,深度最小的那个节点,枚举每个节点作为深度节点的时候的最大权值路径,如果dp2<0则取dp1,否则取dp1+dp2转移 最后更新时间:2019-08-05 23:23:08 这里可以写作者留言,标签和 hexo 中所有变量及辅助函数等均可调用,示例:<%- page.permalink.replace(/index\.html$/, '') %> 赏 Prev cf523C Next cf531F