CF815C Karen and Supermarket [樹形DP]

　　題目傳送門

Karen and Supermarket

?

On the way home, Karen decided to stop by the supermarket to buy some groceries.

She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to?b?dollars.

The supermarket sells?n?goods. The?i-th good can be bought for?ci?dollars. Of course, each good can only be bought once.

Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given?n?coupons. If Karen purchases the?i-th good, she can use the?i-th coupon to decrease its price by?di. Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all?i?≥?2, in order to use the?i-th coupon, Karen must also use the?xi-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).

Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget?b?

?

Input

The first line of input contains two integers?n?and?b?(1?≤?n?≤?5000,?1?≤?b?≤?109), the number of goods in the store and the amount of money Karen has, respectively.

The next?n?lines describe the items. Specifically:

• The?i-th line among these starts with two integers,?ci?and?di?(1?≤?di?<?ci?≤?109), the price of the?i-th good and the discount when using the coupon for the?i-th good, respectively.
• If?i?≥?2, this is followed by another integer,?xi?(1?≤?xi?<?i), denoting that the?xi-th coupon must also be used before this coupon can be used.

?

Output

Output a single integer on a line by itself, the number of different goods Karen can buy, without exceeding her budget.

?

Examples

input

Copy

6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5

output

Copy

4

input

Copy

5 10
3 1
3 1 1
3 1 2
3 1 3
3 1 4

output

Copy

5

?

Note

In the first test case, Karen can purchase the following?4?items:

• Use the first coupon to buy the first item for?10?-?9?=?1?dollar.
• Use the third coupon to buy the third item for?12?-?2?=?10?dollars.
• Use the fourth coupon to buy the fourth item for?20?-?18?=?2?dollars.
• Buy the sixth item for?2?dollars.

The total cost of these goods is?15, which falls within her budget. Note, for example, that she cannot use the coupon on the sixth item, because then she should have also used the fifth coupon to buy the fifth item, which she did not do here.

In the second test case, Karen has enough money to use all the coupons and purchase everything.

---

　　分析：

　　考試的時候遇到這道題結果還是一臉懵逼，果然我$DP$還是太弱了，還是得好好補補。

　　考慮用樹形$DP$，根據題意構建出一棵樹，然后從根節點開始深搜，把每個節點遍歷一遍，然后從葉子節點開始向根節點轉移狀態。

　　定義$f[x][j][0/1]$表示遍歷到了第$x$個商品時已經購買了$j$個商品，$0/1$表示第$x$個商品是否打折。

　　那么狀態轉移方程為：

　　$f[x][j+k][0]=Min(f[x][j+k][0],f[x][j][0]+f[y][k][0]);$

　　$f[x][j+k][1]=Min(f[x][j+k][1],f[x][j][1]+f[y][k][0]);$

　　$f[x][j+k][1]=Min(f[x][j+k][1],f[x][j][1]+f[y][k][1]);$

　　其中$j$和$k$分別表示當前節點和其子節點已經搜過的子樹中購買的商品個數。可能有點繞，可以結合代碼理解。

　　Code：

?

//It is made by HolseLee on 15th Aug 2018
//CF815C
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#define Max(a,b) (a)>(b)?(a):(b)
#define Min(a,b) (a)<(b)?(a):(b)
#define Swap(a,b) (a)^=(b)^=(a)^=(b)
using namespace std;const int N=5005;
int n,m,head[N],siz,w[N],c[N],rt[N];
long long f[N][N][2];
struct Node{int to,nxt;
}edge[N<<1];inline int read()
{char ch=getchar();int num=0;bool flag=false;while(ch<'0'||ch>'9'){if(ch=='-')flag=true;ch=getchar();}while(ch>='0'&&ch<='9'){num=num*10+ch-'0';ch=getchar();}return flag?-num:num;
}inline void add(int x,int y)
{edge[++siz].to=y;edge[siz].nxt=head[x];head[x]=siz;
}void dfs(int x)
{rt[x]=1;f[x][0][0]=0;f[x][1][0]=w[x];f[x][1][1]=c[x];for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;dfs(y);for(int j=rt[x];j>=0;--j)for(int k=0;k<=rt[y];++k){f[x][j+k][0]=Min(f[x][j+k][0],f[x][j][0]+f[y][k][0]);f[x][j+k][1]=Min(f[x][j+k][1],f[x][j][1]+f[y][k][0]);f[x][j+k][1]=Min(f[x][j+k][1],f[x][j][1]+f[y][k][1]);}rt[x]+=rt[y];}
}int main()
{//freopen("shopping.in","r",stdin);//freopen("shopping.out","w",stdout);n=read();m=read();memset(f,127/3,sizeof(f));w[1]=read();c[1]=read();c[1]=w[1]-c[1];int x,y,z;for(int i=2;i<=n;++i){x=read();y=read();z=read();w[i]=x;c[i]=x-y;add(z,i);}dfs(1);for(int i=n;i>=0;--i){if(f[1][i][0]<=m||f[1][i][1]<=m){printf("%d\n",i);break;}}return 0;
}

?

?

?

?