「SDOI2017」苹果树 - 树上依赖背包+多重背包

题目大意

    夏天近了，又到了恋爱的季节，小 Q 家门前的苹果树上结满了红红圆圆的苹果。

    这株苹果树是一个有着$n$个结点的有根树，其中结点被依次编号为$1$至$n$。$1$号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第$i$个结点上有$a_i(a_i>0)$个苹果，每取走其中一个苹果就可以得到$v_i(v_i\gt0)$的幸福度（若在这个结点取走$k\leq a_i$个苹果，则可以收获$kv_i$的幸福度）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。

    现在，给定正整数$k$，请从树上取走若干苹果。如果总计取走了$t$个苹果，且所有取了至少一个苹果的那些结点的最大深度为$h$（这里规定根结点的深度为$1$），则要求$t-h\le k$。问最大可以收获多少的幸福度？（这些幸福度全都归属于恋爱中的小 Q）

---

题目分析

分析限制$t-h\le k$，可以理解为允许免费选择一条最长链，然后剩下的做依赖背包。
显然，这条免费的最长链肯定延伸到叶子结点最优（点权为正），设选择的叶子结点为$end$。
如图，我们将选出的物品以免费最长链为分界分为三部分：

最长链左上方的是第一部分（dfs序小于$end$的点），最长链是第二部分，最长链右下方是第三部分（dfs序大于$end$的点）。

第一部分沿着正Dfs序放物品。
先放不能免费的物品，遍历完所有儿子后加入必选物品。
这样，$i$到根的路径只算了不能免费的部分。

第三部分沿着逆Dfs序放物品。
先遍历所有儿子，然后放入必选的和不能免费的。

这样，使用一二三部分的和更新答案即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=20005,maxnm=26000005;

int n,m,Wid,Len,f[maxnm],g[maxnm],fa[maxn],ans=0;
vector<int> edges[maxn];

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

struct Thing {
	int num,value;
} a[maxn];

#define pii pair<int,int>
#define mp make_pair

void trans(int *f,const Thing& a) {
	deque<pii>Q;
	for(int i=0; i<=m; i++) {
		while(!Q.empty()&&Q.front().first<i-a.num)Q.pop_front();
		while(!Q.empty()&&Q.back().second<=f[i]-i*a.value)Q.pop_back();
		Q.push_back(mp(i,f[i]-i*a.value));
		f[i]=Q.front().second+i*a.value;
	}
}

void Dfs1(int Now) {
	if(a[Now].num)trans(f+Now*Wid,a[Now]);
	for(int Next:edges[Now]) {
		memcpy(f+Next*Wid,f+Now*Wid,Len);
		Dfs1(Next);
		for(int j=1,*p=f+Now*Wid+1,*q=f+Next*Wid; j<=m; j++,p++,q++)*p=max(*p,*q+a[Next].value);
	}
}

void Dfs2(int Now,int sum) {
	sum+=a[Now].value;
	for(int Next:edges[Now]) {
		memcpy(g+Next*Wid,g+Now*Wid,Len);
		Dfs2(Next,sum);
		for(int j=1,*p=g+Now*Wid+1,*q=g+Next*Wid; j<=m; j++,p++,q++)*p=max(*p,*q+a[Next].value);
	}
	if(!edges[Now].size())for(int j=0,*p=f+Now*Wid+m,*q=g+Now*Wid; j<=m; j++,p--,q++)ans=max(ans,*p+*q+sum);
	if(a[Now].num)trans(g+Now*Wid,a[Now]);
}

void Clear() {
	for(int i=1; i<=n; i++)edges[i].clear();
	memset(f+Wid,0,Len);
	memset(g+Wid,0,Len);
	ans=0;
}

int main() {
	int t=Get_Int();
	while(t--) {
		Clear();
		n=Get_Int();
		m=Get_Int();
		Wid=m+1;Len=Wid*sizeof(int);
		for(int i=1; i<=n; i++) {
			fa[i]=Get_Int();
			if(fa[i])AddEdge(fa[i],i);
			a[i].num=Get_Int()-1;
			a[i].value=Get_Int();
		}
		Dfs1(1);
		for(int i=1; i<=n; i++)edges[i].clear();
		for(int i=n; i>=1; i--)if(fa[i])AddEdge(fa[i],i);
		Dfs2(1,0);
		printf("%d\n",ans);
	}
	return 0;
}