1 条题解

  • 0
    @ 2026-11-15 16:24:47

    题目分析

    30pts

    暴力枚举所有可能的联通块进行判定。

    60pts

    f[i][j]f[i][j] 表示考虑了 ii 及其子树内的所有点,且目前以 ii 为根节点的一个联通块权值和恰为 jj 时,可以得到的最多的联通块个数。

    时间复杂度为 O(n2)O(n^2)。

    100pts

    任选点权和为 kk 的连通块,其中 k>2k > 2,那么该连通块至少包含两个点权非零的叶子,否则可以在不改变 kk 的前提下迭代删去点权为 00 的叶 子。 如果至少有一个叶子的点权为 22,那么删去该叶子即可得到点权和为 k−2k − 2 的连通块。 否则所有叶子的点权都为 11,那么同时删去两个叶子即可得到点权 和为 k−2k − 2 的连通块。 因此可以通过树形 DP 求出总和为奇数/偶数的点权和最大的连通块来 O(1)O(1) 判断是否存在点权和为 kk 的连通块,每次一旦发现奇偶性正确且权值 >k>k 则可以贪心直接断开,时间复杂度为 O(n)O(n)。

    • 1

    信息

    ID
    128
    时间
    2000ms
    内存
    1024MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者