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

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

思路解析

代码实现

#include 
   
    #include 
    
     using namespace std;#define ll long longstruct 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/