【2019.8.9 慈溪模拟赛 T2】摘Galo（b）（树上背包）

时间：2021-10-03 08:21:34

树上背包

这应该是一道树上背包裸题吧。

众所周知，树上背包的朴素\(DP\)是\(O(nm^2)\)的。

但对于这种体积全为\(1\)的树上背包，我们可以通过记\(Size\)优化转移时的循环上界，做到\(O(nm)\)的。

呃，复杂度为什么是这样的我也很迷，证明我也不会啊。。。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 100000

#define NK 10200000

#define LL long long

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

#define min(x,y) ((x)<(y)?(x):(y))

#define Gmax(x,y) ((x<(y))&&(x=(y)))

using namespace std;

int n,m,ee,a[N+5],lnk[N+5];struct edge {int to,nxt;}e[N<<1];

class FastIO

{

	private:

		#define FS 100000

		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

		#define tn (x<<3)+(x<<1)

		#define D isdigit(c=tc())

		char c,*A,*B,FI[FS];

	public:

		I FastIO() {A=B=FI;}

		Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}

}F;

class TreeDper//树上背包

{

	private:

		int g[N+5];LL *f[N+5],_f[NK+5];

		I void DP(CI x)

		{

			for(RI i=(g[x]=1,lnk[x]),j,k,lim1,lim2;i;i=e[i].nxt)//枚举儿子

				for(DP(e[i].to),g[x]+=g[e[i].to],j=min(g[x],m);~j;--j)//记Size优化转移

					for(k=min(g[e[i].to],m-j);k;--k) Gmax(f[x][j+k],f[x][j]+f[e[i].to][k]);//记Size优化转移

			Gmax(f[x][1],a[x]);//选自己

		}

	public:

		I void Solve()

		{

			RI i,j;LL ans=0;for(i=1;i<=n;++i) f[i]=&_f[(i-1)*(m+1)+1];//题目中没给出n,k具体范围，只能用指针了

			for(DP(1),i=1;i<=m;++i) Gmax(ans,f[1][i]);printf("%lld",ans);//输出答案

		}

}T;

int main()

{

	freopen("b.in","r",stdin),freopen("b.out","w",stdout);

	RI i,x;for(F.read(n),F.read(m),++m,i=2;i<=n;++i) F.read(x),F.read(a[i]),add(x,i);

	return T.Solve(),0;

}

相关文章