[SDOI2017]苹果树

此题爆肝一个晚上的菜鸡，呜呜呜

题意：luogu P3780

一棵树，每个点都有全值和取它次数的上限。h为你所取的最大深度(根为1），c为你取的个数，满足c-h<=k(k题目给出)

思路：

相当于免费取一条链（尽量长肯定到叶子），然后我么可以想到暴力枚举这条链。
除了链上的点之外的其它点都要满足父子关系。
我一开始想到链上随便选于是枚举链上不免费选的个数，然后后贪心从大到小选，其余的点跑多重背包dp。
当然这样是有问题的，链上的点会作为父亲影响到非链上的点。

ps.树上背包复杂度是\(O(n^2)\),树上多重背包后序遍历dfs序转化后+单调队列优化也是可以\(O(n^2)\),为此我还去学了一下，当然这里是\(O(n*k)\)。

为了满足父子关系又方便搞免费链，每个点拆成2个容量分别为\(1\)和\(a_i-1\)的点，即把\(a_i-1\)挂在\(1\)的点上。
问题轻松转化为：

• 链上的免费的点（不包括挂的）
• 链左边（链叶子的dfs序前）
• 链右边 (邻接表reverse后如上)
  后序遍历一下，搞出dfs序，求一遍dp，具体：
  \(dp[i][j]\)表示dfs序前\(i\)个选\(j\)个的最大价值。
  \(dp[i][j]=max(dp[i-sz[dfn[i]][j],dp[i][j-k])\)其中\(1<=k<=a_{dfn[i]}\)
  单调队列优化后\(O(n*k)\)顺便吐槽毒瘤的数据范围
  我们搞个dp2是在邻接表reverse后再跑一遍（式子同上）
  最后枚举叶链的同时枚举左右两边选的大小就over了
  ……
  我的常数很大，因为拆点，别人跑的都比我快。不拆点也可以做……

code

#include
using namespace std;
const int N=1e5+5;
const int K=5e5+5;
const int NK=60000005;
typedef long long ll;
struct node {
	int x,data;
}Q[K];
int num,n,k,sz[N],p[N],tim,dfn1[N],dfn2[N],dis[N],dp[NK][2],fa[N],a[N],val[N],Out[N];
vector V[N];
inline int Id(int u,int v) {return u*(k+1)+v;}
void dfs1(int u) {
	sz[u]=1;
	for(int i=0;i=0;i--) {
		int v=V[u][i];
		dfs2(v);
	}
	dfn2[u]=++tim;p[tim]=u;
}
void DP(bool f) {
//	for(int i=1;i<=num;i++) printf("%d ",p[i]);
//	puts("");
	for(int i=1;i<=num;i++) {
		int h=1,t=0,u=p[i];
		Q[++t]=(node){0,0};
		for(int j=1;j<=k;j++) {
			while(h<=t&&Q[h].x+a[u]1) {
				++num;V[i].push_back(num); a[num]=a[i]-1;a[i]=1;val[num]=val[i];
			}
		}
//		printf("!\n");
		tim=0;dis[1]=val[1];dfs1(1);DP(0);
//		printf("!\n");
		tim=0;dfs2(1);DP(1);
		for(int i=1;i<=n;i++) {
			if(Out[i])continue;
			for(int j=0;j<=k;j++) {
//				printf("%d %d %d %d %d\n",i,j,dis[i],dp[Id(dfn1[i]-1,j)][0],dp[Id(dfn2[i]-2,k-j)][1]);
				ans=max(ans,dis[i]+dp[Id(dfn1[i]-1,j)][0]+dp[Id(dfn2[i]-sz[i],k-j)][1]);
			}
		}
		printf("%d\n",ans);
		for(int i=1;i<=n;i++) V[i].clear(),Out[i]=0;
		memset(dp,0,sizeof(dp));
	}
	return 0;
}