题解 P3780 【[SDOI2017]苹果树】

感谢管理员的大时限… 这道题终于极限卡常数过了233 _(在我AC这道题的时候它还是道蓝牌题，但是我怎么都觉得假蓝牌题害人啊)_ # ~~我背包今天就是要卡死你~~ 所以说不要觉得背包问题是一个很无脑的dp问题啊…… 就算是纯粹的背包问题，其实也是非常有思维含量的 ## 前置芝士：树的后序遍历 我们一般的dfs序其实是记录入栈顺序 但是其实这样的dfs序是最没用的，唯一的性质也就是一个子树的节点的dfs序是连续的这个性质可以用 但是如果我们不存入栈顺序而是求弹栈顺序呢？ 那么我们会发现，除了dfs序的性质得以保留，而且还多了一个新的性质 **任意一个点i的子树在这个序列上都是一个区间，并且i是区间右端点** ~~(其实dfs序也有，只是是左端点)~~ 而这种求弹栈顺序的得到的序列，在一定程度上部分还原了dfs序的信息，我们称之为后序遍历。 (请牢记后续遍历的性质，这个性质对于做题非常关键！) ______________ ## 本题题解 先让我们理一下题意：树上求背包最大收益，每个物品的体积都是1，同一个物品可以取ai次，并且取儿子必须取父亲，除此之外，我们还可以免费取一条最长链 嗯~ o(*￣▽￣*)o这里我们发现点权都是正的，所以我们可以确定免费的链一定是从**根节点到叶子的一条路径**(因为如果不是叶子的话我们可以继续贪心的向下取) 发现如果没有这个叶子的限制这题似乎还给了一些扑腾的空间，但是加上这个限制之后我们就只能死鱼了……情况开始变得辣手 ### 当问题开始变得辣手的时候，我们要想一些暴力的方法，比如枚举 所以我们枚举每一个叶子到根节点的路径，并且删掉这条路径 这个树大概会被分为4个部分 1.链上免费取的部分 2.链上付费取的部分 3.树左边(这里暂时不理解没关系)的部分 4.树右边的部分 发现4个部分的情况太过复杂，而最为辣手的东西是第2个部分，因为这部分的点甚至不满足树形依赖关系，我们希望通过适(奇)当(技)的(淫)操(巧)作来让这部分东西满足树形依赖关系 我们发现对于所有物品都有这样一个隐含的逻辑关系在 **如果我要取点i的第2个及以后的物品，我首先要选取点i第一个物品** 观察题目中给出的逻辑关系 **如果我要取i的第一个物品，我首先要选取他父亲的第一个物品** 我们发现这个隐含的逻辑关系和题目中的父子关系是一致的 所以我们可以考虑**拆点** 一个点，如果物品数大于1，拆成两个点，一个点是i，物品数只有一个，但是保留所有树上的连边关系，另一个是i'物品数是ai-1不和任何其他点连边，只和i连边并且作为i的儿子出现 这样的话我们的i'就代表了这个点剩下的物品，并且i和i'的父子关系等价的描述了"如果我要取点i的第2个及以后的物品，我首先要选取点i第一个物品"的逻辑关系 那这样的话我们再次枚举路径会发生什么有趣的现象呢？ 观察一下这个两个图，其中的蓝色数字是后续遍历，橙色数字是将临界表全部reverse的后续遍历，黑色点是原来的点，红色点是拆点之后的点   我们会发现一个有趣的事实，树的左半部分(被绿色圈起来的部分)和树的右半部分(被紫色圈起来的部分)刚好是两种后序遍历上一段连续的区间…… 并且，中间剩下的链部分只剩下了黑色点，也就是说，黑链上的东西被孤立了出来，这些东西可全部是免费的…… 此时我们只需要枚举树的左半边选多少和树的右半边选多少个点就行了…… 因为不包含免费部分并且包含了全部的付费部分，所以左边+右边刚好是k个 我们$O(k)$的枚举就行了,这样枚举的总复杂度是$O(nk)$注意到nk是爆炸的$2.5×10^{7}$这种丧病的数据范围，这样我们需要在$O(1)$时间内回答形如“在后续遍历前i个点中选择k个物品的最大收益”这样的问题 那么我们自然而然的想到了dp 我们设$dp_{i,j}$表示决策到了后序遍历第i个点，选取j个物品的最大收益 那么我们枚举这个物品选还是不选，如果不选的话，它的子树全部不可选，而不可选的子树是一段区间，所以只能由$dp_{i-siz_{i},j}$转移过来，如果选的话，我们枚举这个物品选几个 转移方程大概长这样？ # $dp_{i,j}=max_{k=1}^{a_{i}}(dp_{i-1,j-k},dp_{i-siz_{i},j})$ 似乎和多重背包的转移方程很像？ 准确来说除了最后那个$i-siz_{i}$以外是一膜一样吧…… 而这个东西根本不影响多重背包的单调队列优化…… ~~(蛤，你不会多重背包的单调队列优化？，去问度娘，包教包会)~~ (这里默认大家会多重背包的单调队列优化) ~~(不要妄想使用二进制优化，这道题$O(nk)$都吃力别说再加个log了)~~ 所以我们可以做到$O(nk)$的求出每个dp的值 然后我们要先后续跑一边dp，之后把邻接表reverse一遍再跑一边dp 此时我们的$dp_{i,k}$值就是那个“在后续遍历前i个点中选择k个物品的最大收益”的答案 最后一个问题，我们发现这样做的话有些点的父亲是没有被选择的 比如图片中的第9，11，12号点它们的父亲在dp的时候没有确保被选上 ## 醒醒啊，它们的父亲是你枚举的免费点！ 所以可以确保父亲一定被选上了233 另一个问题，我们发现如果枚举叶子i时无脑的认为正着后续遍历区间是i正着的后续遍历序-1，倒着后续遍历区间是i倒着的后续遍历序-1，那么最后会发现他拆点之后的儿子被选了两遍，(比如图中的9/12号点)，因此确定区间的时候需要有一个是减$siz_{i}$的 然后我们的算法复杂度是$O(nk)$的，然而本题的$nk=2.5×10^{7}$这个丧病的nk数值决定了我们的算法需要一些底(大)层(力)优(卡)化(常)，和坚定的(大)信(时)仰(限)才可以避免T飞的惨剧…… ### 一些玄学卡常技巧 1.一维数组模拟二位的映射公式请选用$i×(k+1)+j$因为这样的话你会连续的访问一段内存大大减少二级缓存未命中事件的发生，从而节约一定的常数 2.请存单向边，卡常效果显著 3.如果像我一样使用了vector来存边，那么在清空vector的时候请新建一个空vector再swap两个vector，这样的话可以O(1)完成clear操作 4.不要写双端队列！双端队列的操作也不要封装在结构体里，更不要用stl!所有的操作全部手动inline，包括模拟二维数组的映射函数也是…… 但是代码还是挺短的 上代码~ ```C #include<cstdio> #include<algorithm> #include<vector> using namespace std; const int N=4*1e4+10;const int K=5*1e5+10;const int NK=6*1e7+10; inline void clear(vector <int>& ve){vector <int> emp;swap(emp,ve);}//高速清空函数 vector <int> v[N];int w[N];int a[N];int n;int res;int ctt;int k; int dfn1[N];int dfn2[N];int df1;int df2;int siz[N];int line[N]; int dp1[NK];int dp2[NK];bool lf[N];int nfd1[N];int nfd2[N];int T; int h;int fa[N];int q1[2*K];int q2[2*K];int hed=1;int til=0; inline void dypr(int* dfn,int* dp)//dp的函数 { for(int i=1;i<=ctt;i++) { int v=dfn[i];hed=1;til=1;q1[til]=q2[til]=0;//手动inline了全部的deque操作，凑合着看吧 for(int j=1;j<=k;j++) { hed+=(q1[hed]<j-a[v])?1:0;int val=dp[(i-1)*(k+1)+j]-j*w[v]; dp[i*(k+1)+j]=max(q2[hed]+j*w[v],dp[(i-siz[v])*(k+1)+j]);//单调队列优化转移 while(hed<=til&&q2[til]<=val){til--;}q1[++til]=j;q2[til]=val; } } } inline void clear_all()//清空函数 { for(int i=0;i<=ctt;i++){clear(v[i]);lf[i]=line[i]=siz[i]=0;} for(int i=0;i<=(ctt+1)*(k+1);i++){dp1[i]=dp2[i]=0;} df1=df2=res=ctt=0;h=0; } void dfs1(int x)//正着dfs，原谅我毒瘤压行 { siz[x]=1; for(int i=0;i<v[x].size();i++) {dfs1(v[x][i]);siz[x]+=siz[v[x][i]];}dfn1[++df1]=x;nfd1[x]=df1; } void dfs2(int x)//reverse后dfs { for(int i=v[x].size()-1;i>=0;i--) {line[v[x][i]]=line[x]+w[v[x][i]];dfs2(v[x][i]);} dfn2[++df2]=x;nfd2[x]=df2; } inline void solve() { scanf("%d%d",&n,&k);ctt=n; for(int i=1;i<=n;i++){scanf("%d%d%d",&fa[i],&a[i],&w[i]);lf[fa[i]]=true;} for(int i=1;i<=n;i++)//加边和拆点 { v[fa[i]].push_back(i); if(a[i]>1){a[++ctt]=a[i]-1;a[i]=1;w[ctt]=w[i];v[i].push_back(ctt);} }line[1]=w[1];dfs1(1);dfs2(1);dypr(dfn1,dp1);dypr(dfn2,dp2);//dfs和dp for(int i=1;i<=n;i++)//枚举叶子更新答案 { if(lf[i])continue; for(int j=0;j<=k;j++) {res=max(res,dp1[(nfd1[i]-1)*(k+1)+j]+line[i]+dp2[(nfd2[i]-siz[i])*(k+1)+(k-j)]);} }printf("%d\n",res);//然后靠信仰卡常吧 } int main() {scanf("%d",&T);for(int z=1;z<=T;z++){solve();clear_all();}return 0;}//拜拜程序~ ```