HZOI 可怜与超市

网上搜不着，八成又是哪个学长留下的……

因为考试第二题我们都好不容易才搞懂，学长有给我们扔了几道类似的题。

其实这道题思路挺好想的，就是一些细节还有复杂度比较难弄，好难调啊。

看到题的第一眼以为是树形背包，然后看到b的范围就放弃了。那咋办呢？首先第一维肯定是在树上某个节点，第二维呢？抓住小的干，f[i][j]表示在以i为根的子树里买j个物品花的最少钱数，但是其实还有一点没有考虑，就是子树能不能用优惠券决定于根节点买不买，再加半维？f[i][j][0]表示以i为根的子树里买j个物品花的最少钱数且i不买，f[i][j][1]表示以i为根的子树里买j个物品花的最少钱数且i买，正解就出来了。

　WA20代码：

    for(int i=f(x);i;i=n(i))
    {
        dfs(v(i));
        size[x]+=size[v(i)];
        for(int j=size[x];j;j--)
            for(int k=0;k<=size[v(i)];k++)    
            {
                f[x][j][0]=min(f[x][j][0],f[v(i)][k][0]+f[x][j-k][0]);
                f[x][j][1]=min(f[x][j][1],f[v(i)][k][1]+f[x][j-k][1]);
            }
    }

上面的代码是不是太简单了呀，显然忘东西了呀，WA50代码：

 1 void dfs(int x)
 2 {
 3     size[x]=1;
 4     f[x][0][0]=0,f[x][0][1]=INF,f[x][1][0]=c[x],f[x][1][1]=c[x]-d[x];
 5     if(!f(x))return;
 6     for(int i=f(x);i;i=n(i))
 7     {
 8         dfs(v(i));
 9         size[x]+=size[v(i)];
10         for(int j=size[x];j;j--)
11             for(int k=0;k<=size[v(i)]&&k<=j;k++)    
12             {
13                 f[x][j][0]=min(min(f[x][j][0],f[v(i)][k][0]+f[x][j-k][0]),min(f[v(i)][j][0],f[v(i)][k][0]+f[x][j-k][0]) );
14                 if(j!=k)
15                 f[x][j][1]=min(f[x][j][1],f[v(i)][k][1]+f[x][j-k][1]);
16                 if(j!=k&&j>1&&k>1)    f[x][j][1]=min(f[x][j][1],  min(f[v(i)][j-1][0]+c[i]-d[i],f[x][k][1]+f[v(i)][j-k][0]) );
17             }
18     }
19 }

上面的代码少考虑了在儿子节点不买儿子节点但是卖儿子节点的儿子的情况，改完之后T70的代码：

 1 void dfs(int x)
 2 {
 3     size[x]=1;
 4     f[x][0][0]=0,f[x][0][1]=INF,f[x][1][0]=c[x],f[x][1][1]=c[x]-d[x];
 5     if(!f(x))return;
 6     for(int i=f(x);i;i=n(i))dfs(v(i));
 7     for(int i=f(x);i;i=n(i))
 8     {
 9         size[x]+=size[v(i)];
10         for(int j=size[x];j>=0;j--)
11         for(int k=min(size[v(i)],j);k>=0;k--)    
12         {
13             f[x][j][0]=min(min(f[x][j][0],f[v(i)][k][0]+f[x][j-k][0]),min(f[v(i)][j][0],f[v(i)][k][0]+f[x][j-k][0]));
14             if(j!=k)f[x][j][1]=min( min(f[x][j][1],f[v(i)][k][1]+f[x][j-k][1]) ,f[v(i)][k][0]+f[x][j-k][1]);
15             if(j!=k&&j>1&&k>1)    f[x][j][1]=min(f[x][j][1], f[x][k][1]+f[v(i)][j-k][0] );
16         }
17     }
18 }

其实已经改对了，但是这样的复杂度是$n^3$的，size先加是$n^3$,size后加才是$n^2$，其实就相当于是枚举点对数，所以是$n^2$,但是我这份代码不能在后面加,平局每次j都比后加多枚举一颗子树，所以我尝试着卡一卡，给儿子排序，打的放后边，虽然快了一点，但还是T了，所以又开始了艰辛的改代码，又一次T70：

 1 void dfs(int x)
 2 {
 3     size[x]=1;
 4     f[x][0][0]=0,f[x][0][1]=INF,f[x][1][0]=c[x],f[x][1][1]=c[x]-d[x];
 5     if(!f(x))return;
 6     for(int i=f(x);i;i=n(i))dfs(v(i));
 7     for(int i=f(x);i;i=n(i))
 8     {
 9         size[x]+=size[v(i)];
10         memset(tmp,0x3f,sizeof(tmp));
11         for(int j=0;j<=size[x];j++)
12         for(int k=0;k<=size[v(i)]&&j+k<=size[x]+size[v(i)];k++)
13         {
14             tmp[j+k][0]=min(min(tmp[j+k][0],f[v(i)][k][0]+f[x][j][0]),min(f[v(i)][j+k][0],f[v(i)][k][0]+f[x][j][0]));
15             if(j)tmp[j+k][1]=min(min(tmp[j+k][1],f[v(i)][k][1]+f[x][j][1]),f[v(i)][k][0]+f[x][j][1]);
16         　　 if(j+k!=k&&j+k>1&&k>1) tmp[j+k][1]=min(tmp[j+k][1],f[x][k][1]+f[v(i)][j][0]);
17         }
18         for(int j=0;j<=size[x];j++)
19             f[x][j][0]=min(f[x][j][0],tmp[j][0]),f[x][j][1]=min(f[x][j][1],tmp[j][1]);
20     }
21 }

向上次那样的枚举顺序不能把size放到后边，要枚举j，k向j+k转移，而且这样还要用到辅助数组……

为啥这样还是不能吧size+放到下边呢？把代码中加粗部分加上就行了,我也不知道当时为啥这么沙雕……

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define MAXN 5010
#define LL long long
#define INF 1000000010
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int L=1<<20|1;
char buffer[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
struct edge
{
	int u,v,nxt;
	#define u(x) ed[x].u
	#define n(x) ed[x].nxt
	#define v(x) ed[x].v
}ed[1000000];
int first[MAXN],num_e;
#define f(x) first[x]
struct sor
{int size,id;
	friend bool operator < (sor a,sor b)
	{
		return a.size>b.size;
	}
}so[MAXN];
int n,b;
int c[MAXN],d[MAXN],x[MAXN];
int f[MAXN][MAXN][2],size[MAXN];
void dfs1(int x)
{
	so[x].size=1;so[x].id=x;
	for(int i=f(x);i;i=n(i))
	dfs1(v(i)),so[x].size+=so[v(i)].size;
}
int tmp[MAXN][2];
void dfs(int x)
{
	size[x]=1;
	f[x][0][0]=0,f[x][0][1]=INF,f[x][1][0]=c[x],f[x][1][1]=c[x]-d[x];
	if(!f(x))return;
	for(int i=f(x);i;i=n(i))dfs(v(i));
	tmp[0][0]=0,tmp[0][1]=INF,tmp[1][0]=c[x],tmp[1][1]=c[x]-d[x];
	for(int i=f(x);i;i=n(i))
	{
		memset(tmp,0x3f,sizeof(tmp));
		for(int j=0;j<=size[x]+1;j++)
		for(int k=0;k<=size[v(i)]+1&&j+k<=size[x]+size[v(i)];k++)
		{
			tmp[j+k][0]=min(min(tmp[j+k][0],f[v(i)][k][0]+f[x][j][0]),min(f[v(i)][j+k][0],f[v(i)][k][0]+f[x][j][0]));
			if(j)tmp[j+k][1]=min(min(tmp[j+k][1],f[v(i)][k][1]+f[x][j][1]),f[v(i)][k][0]+f[x][j][1]);
			if(j+k!=k&&j+k>1&&k>1) tmp[j+k][1]=min(tmp[j+k][1],f[x][k][1]+f[v(i)][j][0]);
		}
		size[x]+=size[v(i)];
		for(int j=0;j<=size[x];j++)
			f[x][j][0]=min(f[x][j][0],tmp[j][0]),f[x][j][1]=min(f[x][j][1],tmp[j][1]);
	}
}
inline int read()
{	
	int s=0;char a=getchar();
	while(a<'0'||a>'9')a=getchar();
	while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();}
	return s;
}
inline void add(int u,int v);
signed main()
{
//	freopen("in.txt","r",stdin);

	n=read(),b=read();
	for(int i=1;i<=n;i++)
	{
		if(i==1)c[i]=read(),d[i]=read();
		else
		{
			c[i]=read(),d[i]=read(),x[i]=read();
			add(x[i],i);
		}
	}
	dfs1(1);
	sort(so+1,so+n+1);
	memset(ed,0,sizeof(ed));memset(first,0,sizeof(first));num_e=0;
	for(int i=2;i<=n;i++)
		add(x[so[i].id],so[i].id);
	dfs1(1);
	memset(f,0x3f,sizeof(f));
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		if(min(f[1][i][1],f[1][i][0])>b)
		{printf("%d
",i-1);return 0;}
	}
	cout<<n<<endl;
}
inline void add(int u,int v)
{
	++num_e;
	u(num_e)=u;
	v(num_e)=v;
	n(num_e)=f(u);
	f(u)=num_e;
}