P3925 aaa被续

    • 57通过
    • 543提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 树状数组 树链剖分,树剖 线段树 洛谷原创 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1500ms / 128MB-256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    HansBug持续无聊ing

    题目描述

    由于aaa没有完成HansBug的任务。所以HansBug开始计划着如何续aaa。

    现在HansBug手里有 $ N $ 个aaa,每个aaa有一个码力值。一共存在 $ N - 1 $ 条连接两个aaa的边,故这 $ N $ 个aaa构成一棵有根树,根为1号aaa。

    现在HansBug想要续了这 $ N $ 个aaa。HansBug所采用的策略是,对于第 $ i$ 个aaa,先让他和他的各级子aaa们乖乖♂站好成一队,然后依次续掉。

    经过长期对于aaa码力值的研究,HansBug发现,对于每一队aaa,设有 $n$ 个,码力值依次为 $ v_i $ ,则续了队伍里的第 $ i $ 个aaa所能获得的码力值为 $ v_1 + v_2 + \cdots + v_i $ 。

    然而,aaa之间的关系树相当的复杂,HansBug的智商早已不够用,于是这个任务就交给了你。不过HansBug知道,任何一个aaa都不会有超过5个的直接子aaa

    HansBug想要知道在每次排♂队方法最优的情况下,续了这些aaa最多可以获得的码力值,事成之后分给你100000 % 10点码力值

    输入输出格式

    输入格式:

    第一行包含一个正整数 $ N $ ,表示aaa的个数。

    接下来 $ N-1 $ 行,每行包含两个正整数 $ u, v$ ,代表第 $u $ 个aaa和第 $ v $ 个aaa之间存在从属关系(最高级别的aaa编号为 $ 1$ )

    最后一行包含 $ N $ 个非负整数,依次代表第 $ i $ 个aaa的码力值。

    输出格式:

    输出包含一个整数,打表HansBug续掉全部的aaa之后最多能获得的码力值。

    由于结果较大,所以请对 $ 1000000007 $ 取模 ( $ {10} ^ 9 + 7 $ )

    输入输出样例

    输入样例#1: 复制
    5
    5 3
    1 2
    1 5
    4 5
    3 9 10 4 7 
    
    输出样例#1: 复制
    189
    

    说明

    样例解释:

    故续了5个aaa所得的最大总码力值为:118 + 9 + 10 + 4 + 48 = 189

    对1000000007取模后得到答案189

    数据范围:

    对于30%的数据: $ 1 \leq N \leq 3 \cdot {10}^3 $

    对于50%的数据: $ 1 \leq N \leq 2 \cdot {10}^4 $

    对于70%的数据: $ 1 \leq N \leq {10}^5 $

    对于100%的数据: $ 1 \leq N \leq 5 \cdot {10}^5 $

    对于每一个aaa的码力值 $ a_i $ ,保证 $ 0 \leq a_i \leq {10}^8 $

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。