一类基于值域的伪多项式树上背包（自动机） max-+ 卷积优化
前言
主要以 ABC311EX 为模板，探讨一下这篇 论文 所讲的 HLRecDp。
我们假定值域大于等于点数。
大致说明一下思路，对于题目所描述的问题：树上背包，其中合并需要
题面翻译
-
一棵
n 个点的有根树，每个点有美丽度B_i 、重量W_i 、颜色C_i （0 或1 ），对每个子树求以下问题的答案： -
你可以重复以下操作任意次：选择一个除根以外的点
u ，把u 的孩子都连到u 的父亲上，然后删除u 。 -
最后得到的树应当满足：相邻的点颜色不同、总重量不超过
m 。 -
在上述条件下最大化总美丽度。
-
所有子树的问题是独立的，并不会真的删除点。
-
2\le n\le 200,0\le m \le 5\times 10^4
（来自 jiangly 的倾情奉献）
题解
Part 1. O(n^2C)
我们先只考虑计算以
先做一点前置工作：考虑删点不大好描述，把这个限制改为：选取若干个点，并满足选取的点组成的虚数仍然满足上述条件。因为颜色限制只与选出后的相邻点有关，那么我们可以考虑一个 naive 的 DP:
- 记
dp[x]_{c,i} 表示当前以x 为根的子树中，选择的点中最上面的点的颜色为c ，选择的点的W 总和为i 所得到的最大收益。
那么转移式子也很容易：
（下面我们用
注意到
因此我们只需要考虑两个数组合并的时候的复杂度。因为树有
Part 2.Why the O is to Biggggg
怎么优化？难点在于
那有人问：若你的意思是两个数组中有相当一部分是未被赋值过。那我卷积时只遍历有真实值的位置的复杂度岂不是也是
不妨举个例子：数组
A 和B 合并，考虑加入过B 数组里的两个数(w_1,v_1) 和(w_2,v_2) ，其中w 为重量，v 为权值。
当我直接让
A 与B 合并时，那么可以视作(w_1,v_1),(w_2,v_2),(w_1+w_2,v_1+v_2) 分别单点加入A 数组内。另一种是我把
(w_1,v_1) 和(w_2,v_2) 单点加入A 数组。
发现区别了吗？在后一种方案中，当
那么我们可以将他们本质浪费描述出来：
并且容易发现直接单点加入复杂度为
那么 中国问题的真解决——向美国人民的呼吁 就是彻底抛弃自下而上的 dp 合并方式，转而拥抱单点加入的大军。
Part 3.How to do dan dian jia ru
为了方便直观的表述，我们先把
注意到我们把原题面的限制体现在转移的 Dp 数组个数和能被更新的状态。因此我们只需要形式化的讨论下面伪代码的优化即可。
（接下来我们直接以下面的伪代码考虑更广泛的优化形式，而减少解释题目中的组合意义）
function dfs(c):返回的两个数组同上面分别是 dp[c][0] 和 dp[c][1]
Dp[0] <- (DP table corresponding to empty set) 初始值
Dp[1] <- (DP table corresponding to empty set) 初始值
for d in {children of c} do 枚举儿子
ep = dfs(d)
Dp[0] <- max_plus_convolution(Dp[0], ep[0]) max+ 卷积
Dp[1] <- max_plus_convolution(Dp[1], ep[1]) max+ 卷积
end for
for i = 0 to X - W[c] do
chmax(Dp[C[c]][i + W[c]], Dp[1 - C[c]][i] + B[c]) 加入点 c
end for
return Dp（AT 官方伪代码）
我们先尝试简化问题：如果 Dp 只有一个数组该怎么办？即普通的树上的背包。即：
Dp <- (DP table corresponding to empty set) 初始值
for d in {children of c} do 枚举儿子
ep = dfs(d)
Dp <- max_plus_convolution(Dp, ep) max+ 卷积
end for
for i = 0 to X - W[c] do
chmax(Dp[C[c]][i + W[c]], Dp[1 - C[c]][i] + B[c]) 加入点 c
end for
return Dp因为这只是普通的树上的背包，所以他没有对 dp 提出其他任意的限制，或者说，根节点及其他的子树没有对当前这个子树提出限制，即我们加入的树上物品可以随意。那我们可以直接把子树合并改成子树内的点单点加入：
Dp <- (DP table corresponding to empty set) 初始值
for d in {son of Tree(c)} do 枚举子树内所有儿子
Dp <- add(Dp , d) 把 d 单点加入 dp
end for
for i = 0 to X - W[c] do
chmax(Dp[C[c]][i + W[c]], Dp[1 - C[c]][i] + B[c]) 加入点 c
end for
return Dp那么对于每个节点，都会暴力加入子树内的所有结点，而一共有
n 个节点那么复杂度即O(n^2C) 。有一些显然的优化方法，但我们先略过不谈。
这给了我们一些启发：我们需要自上而下的扫描，但不一定是自上而下的加入。我们需要尽可能的继承之前扫描得到的结果。或许我们需要一些看上去指数级的算法?
那么一个巨佬的想法就是：观察之前的伪代码。
ep = dfs(y)
Dp[0] <- max_plus_convolution(Dp[0], ep[0]) max+ 卷积
Dp[1] <- max_plus_convolution(Dp[1], ep[1]) max+ 卷积举个例子，比如我们想要计算
或者按照组合意义来看，既然子树
那么我们再尝试写出新的伪代码：
function dfs(c, dp)dp 是初值，dfs 返回的值表示在初始数组为 dp 的前提下，加入所有子树内的合法方案后的背包数组。
Dp[0] <- dp
Dp[1] <- dp
for d in {children of c} do
Dp[0] <- dfs(d, Dp[0])[0]
Dp[1] <- dfs(d, Dp[1])[1]
end for
for i = 0 to X - W[c] do
chmax(Dp[C[c]][i + W[c]], Dp[C[c] ^ 1][i] + B[c])
end for
return Dp注意到
其中
Part 4.HLRecDp to you hua it
对于之前极简情况，我们经常运用轻重链剖分来优化时间复杂度到
我们注意到之前的伪代码中：
for d in {children of c} do
Dp[0] <- dfs(d, Dp[0])[0]
Dp[1] <- dfs(d, Dp[1])[1]
end for第一个遍历到的儿子中
function dfs(c, dp)
if c is not leaf then 如果 c 有重儿子
h = (heavy child of c) 重儿子
Dp <- dfs(h, dp) 继承重儿子的贡献
for d in {children of c} / {h} do 计算答案
Dp[0] <- dfs(d, Dp[0])[0]
Dp[1] <- dfs(d, Dp[1])[1]
end for
else
Dp[0] <- dp 直接赋初值
Dp[1] <- dp
end if
for i = 0 to X - W[c] do
chmax(Dp[C[c]][i + W[c]], Dp[C[c] ^ 1][i] + B[c])
end for
return Dp那么还是直接进行复杂度分析：
还是套主定理可以得到：
Part 5.every zishu to solve
我们现在只解决了计算一个点的答案，由于 dfs 被赋了初始值，所以不能直接计算进答案。但我们发现计算
由于
再再再套用主定理可得：
于是这题就在
用指针实现，新人第一次用指针写代码QAQ
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define int long long
using namespace std;
const int N=210,M=5e4+100,inf=1ll<<60;
int DP[N][M],tot;
int *st[N],sz;
void del(int*x){st[++sz]=x;}
int* New(){if(!sz)st[++sz]=DP[tot++];return st[sz--];}
int n,m;
int son[N],fa[N],siz[N];
int A[N],B[N],C[N],ans[N];
vector<int>g[N];
void dfsp(int x,int ff)
{
fa[x]=ff;siz[x]=1;
for(auto y:g[x])
{
dfsp(y,x);siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
if(son[x])g[x].erase(find(g[x].begin(),g[x].end(),son[x]));
}
pair<int*,int*> dfs(int x,int*Dp,bool pd)
{
int *dp[2],*t1,*t2;
if(son[x])tie(dp[0],dp[1])=dfs(son[x],Dp,pd);
else
{
dp[0]=New(),dp[1]=New();
memcpy(dp[0],Dp,sizeof(DP[0])),memcpy(dp[1],Dp,sizeof(DP[0]));
}
for(auto y:g[x])
{
t2=dp[0];tie(dp[0],t1)=dfs(y,t2,0);del(t1);del(t2);
t2=dp[1];tie(t1,dp[1])=dfs(y,t2,0);del(t1);del(t2);
}
for(int i=B[x];i<=m;i++)dp[C[x]][i]=max(dp[C[x]][i],dp[C[x]^1][i-B[x]]+A[x]);
if(pd)for(int i=B[x];i<=m;i++)ans[x]=max(ans[x],dp[C[x]^1][i-B[x]]+A[x]);
return mk(dp[0],dp[1]);
}
signed main()
{
scanf("%lld%lld",&n,&m);
memset(DP[0],0xcf,sizeof(DP[0]));memset(ans,0xcf,sizeof(ans));
for(int i=2,x;i<=n;i++)scanf("%lld",&x),g[x].push_back(i);
dfsp(1,0);
for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&A[i],&B[i],&C[i]);
int *qaq=New();qaq[0]=0;
for(int i=1;i<=n;i++)if(ans[i]==0xcfcfcfcfcfcfcfcf){auto t=dfs(i,qaq,1);del(t.fi);del(t.se);}
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}后记
- 再来一点小拓展，如果变成：
for d in {children of c} do 枚举儿子
ep = dfs(d)
Dp[0] <- max_plus_convolution(Dp[0], max(ep[0],ep[1])) max+ 卷积
Dp[1] <- max_plus_convolution(Dp[1], ep[1]) max+ 卷积怎么做？由于这个取 max 的限制只是在对根的转移有效，所以可以写成：
for d in {children of c} do
Dp[0] <- max(dfs(d, Dp[0])[0],dfs(d,Dp[0])[1])
Dp[1] <- dfs(d, Dp[1])[1]- 如果变成：
for d in {children of c} do 枚举儿子
ep = dfs(d)
Dp[1] <- max_plus_convolution(Dp[1], ep[1]) max+ 卷积
Dp[2] <- max_plus_convolution(Dp[2], ep[2]) max+ 卷积
...
Dp[k] <- max_plus_convolution(Dp[k], ep[k]) max+ 卷积怎么办？正常套即可：
for d in {children of c} do
Dp[0] <- dfs(d, Dp[0])[0]
Dp[1] <- dfs(d, Dp[1])[1]
...
Dp[k] <- dfs(d, Dp[k])[k]复杂度即变为
- 如果变成：
for d in {children of c} do 枚举儿子
ep = dfs(d)
Dp[0] <- max_plus_convolution(Dp[0],Dp[1],ep[0]) max+ 卷积
Dp[1] <- max_plus_convolution(Dp[1], ep[1]) max+ 卷积
怎么办？WC 不会，润了润了...
另外，乘法卷积也可以套这玩意，但是不如直接上 FFT。感觉最关键的还是抽象初值。