本文共 2336 字，大约阅读时间需要 7 分钟。

这道题目要求我们在一棵有根树的子树中选择一些点，使得它们的花费总和不超过给定的值，并且它们的个数乘以贡献值尽可能大。我们可以通过贪心算法和左偏树的数据结构来高效解决这个问题。

思路解析

代码实现

#include 
   
    
#include 
    
     
using namespace std;
#define ll long long
struct road {
    ll to, nxt;
} e[300001];
struct node {
    ll l, r, key, dis, num, sum;
} tree[2000001];
ll n, m, tot, y, rt[100001];
ll c[100001], l[100001];
ll le[100001], fa[100001];
ll ans;
void add(ll x, ll y) {
    e[++KK] = { y, le[x] };
    le[x] = KK;
}
ll make_tree(ll x) {
    tree[++tot] = { 0, 0, c[x], -1, 1, c[x] };
    return tot;
}
ll merge(ll x, ll y) {
    if (!x) return y;
    if (!y) return x;
    if (tree[x].key < tree[y].key) {
        swap(x, y);
    }
    tree[x].r = merge(tree[x].r, y);
    if (tree[tree[x].l].dis < tree[tree[x].r].dis) {
        swap(tree[x].l, tree[x].r);
    }
    tree[x].dis = tree[tree[x].r].dis + 1;
    tree[x].num = tree[tree[x].l].num + tree[tree[x].r].num + 1;
    tree[x].sum = tree[tree[x].l].sum + tree[tree[x].r].sum + tree[x].key;
    return x;
}
void insert(ll x, ll Y) {
    ll X = make_tree(x);
    Y = merge(X, Y);
}
ll delete_max(ll x) {
    return merge(tree[x].l, tree[x].r);
}
void dfs(ll now, ll father) {
    fa[now] = father;
    for (ll i = le[now]; i; i = e[i].nxt) {
        if (e[i].to != father) {
            dfs(e[i].to, now);
            rt[now] = merge(rt[now], rt[e[i].to]);
            while (tree[rt[now]].sum > m) {
                rt[now] = delete_max(rt[now]);
            }
            ans = max(ans, l[now] * tree[rt[now]].num);
        }
    }
}
int main() {
    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= n; ++i) {
        scanf("%lld %lld %lld", &y, &c[i], &l[i]);
        add(y, i);
    }
    for (ll i = 1; i <= n; ++i) {
        rt[i] = make_tree(i);
        if (tree[i].sum > m) {
            rt[i] = delete_max(rt[i]);
        }
    }
    dfs(1, 0);
    printf("%lld", ans);
    return 0;
}
    
   

总结

通过贪心算法和左偏树的数据结构，我们可以高效地解决这道题。贪心策略确保我们每次选择花费最小的点，从而最大化个数乘以贡献的值。左偏树的合并与删除操作优化了数据结构的性能，使得算法在大规模数据下依然高效。

转载地址：http://vovh.baihongyu.com/