1 solutions

  • 0
    @ 2026-9-18 18:17:46

    决策是考虑进入每个点之后选子树的顺序。

    子树内部显然用内部的最优方案。

    然后子树之间的贡献是先走的子树的大小乘后走的子树的权值和。

    所以按照子树大小除以权值和从大到小排序访问就是最优的。可以用调整法证明贪心是对的。

    时间复杂度 O(nlog⁡n)O(n\log n)。

    • 1

    Information

    ID
    43
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    (None)
    Tags
    (None)
    # Submissions
    0
    Accepted
    0
    Uploaded By