#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
struct {
    int l, r, su;
    long long ma, mx;
    // su ma 表示没满的求和和最大值
    // mx 表示种满的最大值
} t[N << 2];
struct retu {
    int sum;
    long long val;
} tmp;
int n, k, fee;
void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}
inline void pushup(int p) {
    t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx);
    if (t[p << 1].ma < t[p << 1 | 1].ma)
        t[p].ma = t[p << 1 | 1].ma, t[p].su = t[p << 1 | 1].su;
    else if (t[p << 1].ma > t[p << 1 | 1].ma)
        t[p].ma = t[p << 1].ma, t[p].su = t[p << 1].su;
    else {
        if (t[p << 1].su > t[p << 1 | 1].su)
            t[p].ma = t[p << 1 | 1].ma, t[p].su = t[p << 1 | 1].su;
        else
            t[p].ma = t[p << 1].ma, t[p].su = t[p << 1].su;
    }
}
void update(int p, int pl, long long val, int sum) {
    if (t[p].l == t[p].r) {
        if (sum == k)
            t[p].mx = val;
        else if (t[p].ma < val || (t[p].ma == val && t[p].su > sum))
            t[p].ma = val, t[p].su = sum;
        return;
    }
    if (pl <= ((t[p].l + t[p].r) >> 1))
        update(p << 1, pl, val, sum);
    else
        update(p << 1 | 1, pl, val, sum);
    pushup(p);
}
inline retu max(const retu& a, const retu& b) {
    return a.val > b.val ? a : (a.val < b.val ? b : (a.sum > b.sum ? b : a));
}
retu query(int p, int l, int r) {
    if (t[p].l >= l && t[p].r <= r)
        return (retu){t[p].su, t[p].ma};
    retu reu = (retu){0, 0};
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid)
        reu = query(p << 1, l, r);
    if (r > mid)
        reu = max(reu, query(p << 1 | 1, l, r));
    return reu;
}
signed main() {
    scanf("%d%d", &n, &k);
    build(1, 1, n);
    // 1
    scanf("%d", &fee);
    if (fee > 0)
        update(1, 1, fee, 1);
    // 1
    if (n >= 2) { // 2
        scanf("%d", &fee);
        if (fee > 0)
            update(1, 2, fee, 1);
    } // 2
    for (int i = 3; i <= n; i++) {
        scanf("%d", &fee);
        if (fee > 0) {
            tmp = query(1, 1, i - 2);
            update(1, i, fee + tmp.val, tmp.sum + 1);
        }
    }
    printf("%lld", max(t[1].mx, t[1].ma));
    return 0;
}

大致思路：

$i$ 位置读入收益 $fee$ 后寻找 $[1,i-2]$ 区间（$[1,i-1)$）内最大值（得到最大值所种的树的数量 $< k$），然后用这个最大值转移到当前位置并更新 dp 值和线段树，最后在整个区间里找到最大值作为答案。

因为写的 $[1,i-2]$，所以把第一个和第二个位置拿出来特判了一下。

求证伪是因为题解里没找到一篇线段树优化的感觉是假的，但是自己随手造的几组数据都过了。