P4845 LJJ爱数树 题解
一休哥777
·
·
题解
LJJ爱数树
树形 dp 。设计状态的时候比较曲折：由于较浅的节点布置一个摄像头之后会有一些较深的未被覆盖到的节点产生贡献，如果还是要每次精确计算出放置一个摄像头后新产生的贡献大小，对于子树内需要知道有多少会被他覆盖到的节点还没有被其他摄像头覆盖。后面的那个信息是无法直接转移的，因为转移时每次需要恰好减去一层未被覆盖的点的权值和，导致需要记录每一层的权值和，状态数 $n^r$，不能接受。
于是我们提前对于每一个点计算贡献。对于每一个点，在 dp 的时候我们强制要求他最终会不会产生贡献，也就是最终会不会被覆盖，如果会并且当前未被子树内的摄像头覆盖，就一定要让子树外的某一个摄像头覆盖到他。具体的，设 $f_{i,j,k1,k2}$ 表示 $i$ 子树内目前放置了 $j$ 个摄像头，最深的需要贡献但仍未贡献的节点距 $i$ 节点的距离为 $k1$，最浅的摄像头距 $i$ 节点的距离为 $k2$，当前贡献和的最大值。
考虑优化。上述状态成立的一个条件是 $k1+k2 > r$，否则最深的需要贡献的节点已经被覆盖。对于当前子树内未被覆盖的最深的需要贡献的节点需要子树外的一个摄像头覆盖到他，设子树外的距 $i$ 最近的摄像头与 $i$ 距离为 $w$ ，那么 $k1+w\le r$ 。联立二式得 $k2 > w$ 。什么意思？子树内的摄像头覆盖的子树内的节点的贡献已经全部计算过了，他剩余的唯一的价值只有可能会覆盖到子树外的点产生贡献。但是由于我们钦定了子树内的另一个点一定要贡献，导致子树外一定会有另外一个摄像头，而且 $w < k2$ ，说明子树内的那个摄像头会覆盖的子树外的部分，也一定可以被那个子树外的摄像头覆盖。这么看来子树内的摄像头已经完全没有存在的必要了，我们也不需记录他的信息。换句话说，正因为我们钦定了子树内的一个点必须贡献，而子树内的摄像头又无法覆盖到这个点，导致必定会有子树外的一个摄像头在子树外的价值大于这个子树内的摄像头的价值，于是可以直接扔掉这些子树内的摄像头，他们已经没有后续使用价值了。而如果子树内没有需要贡献但尚未贡献的节点，子树内的摄像头仍有价值，我们仍需记录。
缩减状态后，设 $f_{i,j,k,0/1}$ 表示 $i$ 子树内目前放置了 $j$ 个摄像头，当 $op=0$ 表示子树内尚有需要但未被贡献的节点，其最深的一个到 $i$ 的距离为 $k$，当 $op=1$ 表示子树内没有需要但未被贡献的节点，最浅的一个摄像头到 $i$ 的距离为 $k$。下文给出转移时的伪代码：
```
for j:[0,min(siz[i],K)]for k:[0,R+1]for op:[0,1]
for j_:[0,min(siz[v],K)]for k_:[0,R+1]for op_:[0,1]{
if op==1&&op_==1 : op'=1,k'=min(k,k_+1)
if op==0&&op_==1 :
if(k+k_+1<=R) : op'=1,k'=k_+1
else : op'=0,k'=k
if op==1&&op_==0 :
if(k+k_+1<=R) : op'=1,k'=k
else : op'=0,k'=k_+1
if op==0&&op_==0 : op'=0,k'=max(k,k_+1)
(i,j,k,op)+(v,j_,k_,op_)->(i,j+j_,k',op')
}
```
其中 $(j,k,op)$ 枚举了当前 $i$ 的所有状态，$(j\_,k\_,op\_)$ 枚举了当前 $i$ 的一个儿子 $v$ 的所有状态，经过讨论后这两个状态应该转移到 $(j',k',op')$ 状态。分析复杂度：枚举双重 $j$ 的复杂度均摊到整个树形 dp 上后是 $O(nk)$ 的。具体的原因和证明可以从另外的一些树上背包博客了解，或是参考另外一道题：[\[JSOI2018\] 潜入行动](https://www.luogu.com.cn/problem/P4516)，那里的题解区有详细的说明，这里不再赘述。枚举双重 $k$ 的复杂度为 $O(r^2)$ ，总时间复杂度为 $O(nkr^2)$ = $O(n^2r)$ = $O(n^3)$。但是我们发现，对于转移到的 $k'$，$k' = k$ 或 $k' = k \_ +1$，并且每个分类讨论处都可以推出对于一个 $k$，$k\_$ 满足什么条件时 $k'=k$，反之亦然。推出的条件都对应着前缀最大值或后缀最大值，于是分别讨论 $k' = k$ 和 $k' = k \_ +1$，前后缀最大值优化 dp，时间复杂度 $O(nrk)$ = $O(n^2)$。
给出一个代码实现：并没有对每个转移做更加细致的讨论，写的比较格式化，看起来比较臃肿。但是关键点只是在对应的公式的计算，还算清晰。
```cpp
void dfs(int x,int faa){
s[x]=1;
f[x][Dui[0][R+1][1]]=0;// no anything
f[x][Dui[1][0][1]]=a[x];// there is one
f[x][Dui[0][0][0]]=a[x];// prepare one node
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint op:{0,1})pref[x][Dui[j][0][op]]=f[x][Dui[j][0][op]];
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint k=1;k<=R+1;k++)for(rint op:{0,1})pref[x][Dui[j][k][op]]=max(pref[x][Dui[j][k-1][op]],f[x][Dui[j][k][op]]);// pre max
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint op:{0,1})suff[x][Dui[j][R+1][op]]=f[x][Dui[j][R+1][op]];
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint k=R;k>=0;k--)for(rint op:{0,1})suff[x][Dui[j][k][op]]=max(suff[x][Dui[j][k+1][op]],f[x][Dui[j][k][op]]);// suf max
for(rint v:b[x])if(v!=faa){
dfs(v,x);
for(rint i=0;i<=cnt;i++)g[i]=-1e9;
// find all about k using premax and sufmax
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint k=0;k<=R+1;k++)for(rint op:{0,1})
for(rint j_=0;j_<=s[v]&&j+j_<=K;j_++)/*for(rint k_=0;k_<=R+1;k_++)*/for(rint op_:{0,1}){
rint J_=j+j_,k_,OP_;
if(op&&op_){
OP_=1;k_=k-1;
if(k_<0)k_=0;g[Dui[J_][k][OP_]]=max(g[Dui[J_][k][OP_]],f[x][Dui[j][k][op]]+suff[v][Dui[j_][k_][op_]]);
}
if(!op&&op_){
OP_=0;k_=R-k;
if(k_<0)k_=0;g[Dui[J_][k][OP_]]=max(g[Dui[J_][k][OP_]],f[x][Dui[j][k][op]]+suff[v][Dui[j_][k_][op_]]);
}
if(op&&!op_){
OP_=1;k_=R-k-1;
if(k_>=0)g[Dui[J_][k][OP_]]=max(g[Dui[J_][k][OP_]],f[x][Dui[j][k][op]]+pref[v][Dui[j_][k_][op_]]);
}
if(!op&&!op_){
OP_=0;k_=k-1;
if(k_>=0)g[Dui[J_][k][OP_]]=max(g[Dui[J_][k][OP_]],f[x][Dui[j][k][op]]+pref[v][Dui[j_][k_][op_]]);
}
}
// find all about k_
for(rint j=0;j<=s[x]&&j<=K;j++)/*for(rint k=0;k<=R+1;k++)*/for(rint op:{0,1})
for(rint j_=0;j_<=s[v]&&j+j_<=K;j_++)for(rint k_=0;k_<=R;k_++)for(rint op_:{0,1}){
rint J_=j+j_,k,OP_;
if(op&&op_){
OP_=1;k=k_+1;
g[Dui[J_][k_+1][OP_]]=max(g[Dui[J_][k_+1][OP_]],suff[x][Dui[j][k][op]]+f[v][Dui[j_][k_][op_]]);
}
if(!op&&op_){
OP_=1;k=R-k_-1;
if(k>=0)g[Dui[J_][k_+1][OP_]]=max(g[Dui[J_][k_+1][OP_]],pref[x][Dui[j][k][op]]+f[v][Dui[j_][k_][op_]]);
}
if(op&&!op_){
OP_=0;k=R-k_;
g[Dui[J_][k_+1][OP_]]=max(g[Dui[J_][k_+1][OP_]],suff[x][Dui[j][k][op]]+f[v][Dui[j_][k_][op_]]);
}
if(!op&&!op_){
OP_=0;k=k_+1;
g[Dui[J_][k_+1][OP_]]=max(g[Dui[J_][k_+1][OP_]],pref[x][Dui[j][k][op]]+f[v][Dui[j_][k_][op_]]);
}
}
s[x]+=s[v];
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint k=0;k<=R+1;k++)for(rint op:{0,1})f[x][Dui[j][k][op]]=max(f[x][Dui[j][k][op]],g[Dui[j][k][op]]);
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint op:{0,1})pref[x][Dui[j][0][op]]=f[x][Dui[j][0][op]];
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint k=1;k<=R+1;k++)for(rint op:{0,1})pref[x][Dui[j][k][op]]=max(pref[x][Dui[j][k-1][op]],f[x][Dui[j][k][op]]);// pre max
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint op:{0,1})suff[x][Dui[j][R+1][op]]=f[x][Dui[j][R+1][op]];
for(rint j=0;j<=s[x]&&j<=K;j++)for(rint k=R;k>=0;k--)for(rint op:{0,1})suff[x][Dui[j][k][op]]=max(suff[x][Dui[j][k+1][op]],f[x][Dui[j][k][op]]);// suf max
}
}
```
还是赘述一下那个树上背包 $O(nk)$ 的复杂度的地方吧，但是我抄一段题解：[树形背包的复杂度-CF1097G Vladislav and a Great Legend-解题报告](https://www.luogu.com.cn/blog/i207M/shu-xing-bei-bao-di-fu-za-du-cf1097g-vladislav-and-a-great-legend-xi)，以下是原文摘抄：
然后发现每次循环 $\min(sz[v],K)$ 就可以保证复杂度了。
我们现在证明一下复杂度：
首先考虑合并两个子树 A,B ( A dfs 序在前，B 在后)的复杂度 $O(\min(sz[A],K)\times \min(sz[B],K))$，可以理解为：从 A 的 dfs 序选出后 $K$ 个，从 B 的 dfs 序选出前 $K$ 个，然后它们两两配对起来的方案数。
这样，一个点 x 只会和 dfs 序相邻的左右 $2k$ 个（一共 $4k$ ）个点 y 匹配，因为再远了，要么 x 不是所在子树的 dfs 序后 k 个，要么 y 不是所在子树的 dfs 序前 $k$ 个。
因此，总复杂度为 $O(nk)$ 。