Description

在一个忍者的帮派里, 一些忍者们被选中派遣给顾客, 然后依据自己的工作获取报偿. 在这个帮派里, 有一名忍者被称之为 Master. 除了 Master 以外, 每名忍者都有且仅有一个上级. 为保密, 同时增强忍者们的领导力, 所有与他们工作相关的指令总是由上级发送给他的直接 下属, 而不允许通过其他的方式发送. 现在你要招募一批忍者, 并把它们派遣给顾客. 你需要为每个被派遣的忍者 支付一定的薪水, 同时使得支付的薪水总额不超过你的预算. 另外, 为了发送指令, 你需要选择一名忍者作为管理者, 要求这个管理者可以向所有被派遣的忍者 发送指令, 在发送指令时, 任何忍者 (不管是否被派遣) 都可以作为消息的传递人. 管理者自己可以被派遣, 也可以不被派遣. 当然, 如果管理者没有被排遣, 就不需要支付 管理者的薪水. 你的目标是在预算内使顾客的满意度最大. 这里定义顾客的满意度为派遣的 忍者总数乘以管理者的领导力水平, 其中每个忍者的领导力水平也是一定的. 写一个程序, 给定每一个忍者 \(i\) 的上级 \(B_i\), 薪水 \(C_i\), 领导力 \(L_i\), 以及支付给忍者们的薪水总预算 \(m\), 输出在预算内满足上述要求时顾客满意度的最大值.

Input

从标准输入读入数据.

第一行包含两个整数 \(n, m\), 其中 \(n\) 表示忍者的个数,\(m\) 表示薪水的总预算.

接下来 \(n\) 行描述忍者们的上级、薪水以及领导力. 其中的第 \(i\) 行包含三个整数 \(B_i, C_i, L_i\) 分别表示第 \(i\) 个忍者的上级, 薪水以及领导力. Master 满足 \(B_i=0\), 并且每一个忍者的老板的编号一定小于自己的编号 \(B_i \lt i\).

Output

输出一个数, 表示在预算内顾客的满意度的最大值.

Sample Input


5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Sample Output

6

Data Range

数据包括这些内容:

  • \(1 \leq n \leq 10^5\), 代表忍者的个数;
  • \(1 \leq m \leq 10^9\), 代表薪水的总预算;
  • \(0 \leq B_i \lt i\), 代表忍者的上级的编号;
  • \(1 \leq C_i \leq m\), 代表忍者的薪水;
  • \(1 \leq L_i \leq 10^9\), 代表忍者的领导力水平.

Explanation

看来不同人对于暴力的概念其实是不同的......

@hld67890 说其实 (傻逼的) 暴力做法是 \(O(n^2)\) 的, 而暴力做法是 \(O(n \log n)\) 的. 然而我只能想到 \(O(n m)\) 的做法所以我比傻逼还智障~

其实本身用 map 水一下就可以过去的, 因为数据实在是比较离散, 根本没必要开一个 \(O(m)\) 的大数组用来存东西. 然而在 DFS 的过程中合并这些数据的代价还是太高, 所以我们需要一个 能够在最多 \(O(\log n)\) 时间内合并数据的数据结构.

这个数据结构就是左偏树.

有关左偏树的文章, 看这里就可以了:左偏树的特点及其应用.doc

其他的没有必要多讲了吧, 如果这篇论文都看不懂那可以直接回去学文化课了对吧......

顺便吐槽一句, 我的代码实在太 OOP 以至于比黄学长的代码长一倍半.

数组没有开到 \(100100\) 少 \(\frac{9}{10}\) 导致我花了三个小时调数据生成器最后无功而返.

不过如果把生成树这个东西加到 pydatagen 里面会方便不少.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 100100, maxm = 5001000;

template <typename _T>
struct tnode {
    tnode *lc, *rc;
    int dist;
    _T val;
};

template <typename _T>
tnode<_T>* make_tree(_T val)
{
    tnode<_T>* p = new tnode<_T>;
    p->lc = p->rc = NULL;
    p->val = val;
    p->dist = 0;
    return p;
}

template <typename _T>
tnode<_T>* merge(tnode<_T>* a, tnode<_T>* b)
{
    // Nullification of merging
    if (a == NULL) return b;
    if (b == NULL) return a;
    // Ensure heap properties
    if (a->val < b->val)
        swap(a, b);
    // Recursive merging
    a->rc = merge(a->rc, b);
    // Maintain Leftist tree properties
    if (a->lc ? a->lc->dist : 0 < a->rc ? a->rc->dist : 0)
        swap(a->lc, a->rc);
    // Update distance
    a->dist = a->rc ? a->rc->dist + 1 : 0;
    return a;
}

class mergable_heap
{
protected:
    tnode<int> *root;
    lli sum;
    int ncnt;
public:
    void clear(void)
    {
        root = NULL;
        sum = 0;
        ncnt = 0;
        return ;
    }
    bool empty(void)
    {
        return ncnt == 0;
    }
    size_t size(void)
    {
        return ncnt;
    }
    lli get_sum(void)
    {
        return sum;
    }
    void push(int val)
    {
        tnode<int> *nd = make_tree(val);
        root = merge(root, nd);
        sum += val;
        ncnt += 1;
        return ;
    }
    int top(void)
    {
        if (!root)
            return 0;
        int val = root->val;
        return val;
    }
    void pop(void)
    {
        if (!root)
            return ;
        int val = root->val;
        root = merge(root->lc, root->rc);
        sum -= val;
        ncnt -= 1;
        return ;
    }
    friend mergable_heap merge(mergable_heap ha, mergable_heap hb)
    {
        tnode<int> *nroot = merge(ha.root, hb.root);
        mergable_heap hc;
        hc.root = nroot;
        hc.sum = ha.sum + hb.sum;
        hc.ncnt = ha.ncnt + hb.ncnt;
        return hc;
    }
    mergable_heap(void)
    {
        this->clear();
        return ;
    }
};

class TreeDP
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int ecnt, root;
    lli mx, res;
    edge *edges[maxn], epool[maxn<<1];
    int C[maxn], L[maxn];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    mergable_heap dfs(int p)
    {
        mergable_heap hp;
        hp.push(C[p]);
        // Joining child heaps
        for (edge *ep = edges[p]; ep; ep = ep->next) {
            mergable_heap nhp = dfs(ep->v);
            hp = merge(hp, nhp);
        }
        // Removing large values
        while (hp.get_sum() > mx)
            hp.pop();
        // Updating best answer
        res = max(res, (lli)hp.size() * L[p]);
        return hp;
    }
    lli eval(void)
    {
        res = 0;
        dfs(root);
        return res;
    }
} td;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    td.mx = m;
    for (int i = 1, b; i <= n; i++) {
        scanf("%d%d%d", &b, &td.C[i], &td.L[i]);
        if (b > 0)
            td.add_edge(b, i);
        else
            td.root = i;
    }
    lli res = td.eval();
    printf("%lld\n", res);
    return 0;
}