Fork me on GitHub

cf526D

字数统计: 203字   |   阅读时长≈ 1分
转移自老blog

cf526D

链接

题意

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

题解

        随便找个节点当根，dp1[i]代表以i为根的子树上，经过i点，走向子树的路径的最大权值，dp2[i]为次大。得到此数组之后，定义路径的深度节点为路径上的所有节点中，深度最小的那个节点，枚举每个节点作为深度节点的时候的最大权值路径，如果dp2<0则取dp1,否则取dp1+dp2转移
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、聚合支付、
公众号开发、开源爱好者、Linux

联系QQ:2434387555

很惭愧

只做了一点微小的工作
谢谢大家