Description：

给一棵树，每个点上有价值为 $v_i$ 的 $a_i$ 个物品，给定 $m$ ，取走若干个物品，要求取走物品数 $-$ 至少取了一个物品的点的最大深度 $\leqslant m$ ，并且每个点如果取了父亲节点也必须取，求最大收益。

$1\leqslant nm\leqslant 2.5\times 10^7$

Solution：

发现这个问题等价于给一棵树先免费选一条链，然后再选不超过 $m$ 个物品，由于贪心我们肯定最后选到了一个叶子，还是由于贪心我们选的这条链一定是最长的，不然的话我们把他替换成一个更长的链会更优，也就是说我们并没有保证条件一定成立，但是最后找到的最优解一定是合法的，然后我们发现我们并没有什么好的算法可以确定这条链，因此我们可以暴力枚举他，花费 $O(n)$ 的时间，然后在链上的点可以免费取一次，链上的点可以付费取 $a_i-1$ 次，链左边和右边各可以付费取 $a_i$ 次，不难发现链上付费的那部分非常不好做，因为他甚至不满足树形依赖关系，这个时候题解有一个很巧妙的思路就是拆点，把所有大于 $1$ 的点都拆成两个点，一个代表第一个物品，和父亲节点的第一个物品连边，另一个代表剩下的 $a_i-1$ 个物品，和第一个点连边，然后画个图就会发现如果我们采用后续遍历那么所有需要付费的部分一定是正序访问邻接表的一个前缀和后续访问邻接表的一个后缀，因此两部分 $O(m)$ 的背包合并就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

    register int res = 0,f = 1;register char c = getchar();

    while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

    while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

    return res * f;

}

int n,m;

#define MAX 51000000

#define MAXN 40010

int f1[MAX],f2[MAX];

int id(int x,int y){return x * (m + 1) + y;}

vector<int> g[MAXN];

void add(int a,int b){g[a].push_back(b);return;}

int a[MAXN],v[MAXN];

int tot;

int dfn1[MAXN],dfn2[MAXN],pos1[MAXN],pos2[MAXN];

int val[MAXN],siz[MAXN];

int dfs1(int k,int sum)

{

    sum += v[k];val[k] = sum;siz[k] = 1;

    dfn1[++dfn1[0]] = k;pos1[k] = dfn1[0];

    for(vector<int>::iterator it = g[k].begin();it != g[k].end();++it)siz[k] += dfs1(*it,sum);

    return siz[k];

}

void dfs2(int k)

{

    for(vector<int>::iterator it = g[k].begin();it != g[k].end();++it)dfs2(*it);

    dfn2[++dfn2[0]] = k;pos2[k] = dfn2[0];

    return;

}

bool leaf[MAXN];

#define MAXK 500010

int q[MAXK],head,tail;

#define INF 0x3f3f3f3f

void work()

{

    scanf("%d%d",&n,&m);

    tot = n;

    for(int i = 1;i <= n;++i)leaf[i] = true;

    for(int i = 1;i <= n;++i)

    {

        int fa = rd();

        if(fa != 0)add(fa,i);

        leaf[fa] = false;

        a[i] = rd();v[i] = rd();

        if(a[i] != 1)

        {

            add(i,++tot);

            a[tot] = a[i] - 1;v[tot] = v[i];

            a[i] = 1;

        }

    }

    dfs1(1,0);

    dfs2(1);

    for(int i = tot;i >= 1;--i)

    {

        int k = dfn1[i];

        head = 1;tail = 0;

        q[++tail] = 0;

        for(int x = 1;x <= m;++x)

        {

            while(head <= tail && q[head] < x - a[k])++head;

            f1[id(i,x)] = max(f1[id(i + siz[k],x)],f1[id(i + 1,q[head])] - q[head] * v[k] + x * v[k]);

            while(head <= tail && f1[id(i + 1,q[tail])] - q[tail] * v[k] <= f1[id(i + 1,x)] - x * v[k])--tail;

            q[++tail] = x;

        }

    }

    for(int i = 1;i <= tot;++i)

    {

        int k = dfn2[i];

        head = 1;tail = 0;

        q[++tail] = 0;

        for(int x = 1;x <= m;++x)

        {

            while(head <= tail && q[head] < x - a[k])++head;

            f2[id(i,x)] = max(f2[id(i - siz[k],x)],f2[id(i - 1,q[head])] - q[head] * v[k] + x * v[k]);

            while(head <= tail && f2[id(i - 1,q[tail])] - q[tail] * v[k] <= f2[id(i - 1,x)] - x * v[k])--tail;

            q[++tail] = x;

        }

    }

    int ans = 0;

    for(int i = 1;i <= n;++i)

    {

        if(!leaf[i])continue;

        int sum = 0;

        for(int l = 0;l <= m;++l)

        {

            sum = max(sum,f1[id(pos1[i] + 1,l)] + f2[id(pos2[i] - siz[i],m - l)]);

        }

        ans = max(ans,sum + val[i]);

    }

    for(int i = 0;i <= n;++i)g[i].clear();

    dfn1[0] = dfn2[0] = 0;

    for(int i = 1;i <= tot;++i)dfn1[i] = dfn2[i] = pos1[i] = pos2[i] = 0,leaf[i] = false;

    for(int i = 0;i <= tot;++i)for(int j = 0;j <= m;++j)f1[id(i,j)] = f2[id(i,j)] = 0;

    cout << ans << endl;

    return;

}

int main()

{

    int testcases = rd();

    while(testcases--)work();

    return 0;

}