Aly_

树上背包 + Max 卷积

题意简述

​ 给一棵树，要求在其上划出若干条点不相交路径（以下称为 “ 好链 ” ，对应地，称未被划分到任意一条好链的边为不好的边），使得所有点到根路径上的极长不好子链条数的最大值最小，并求出达到这个最小值的方案数。

分析

​ 首先最小值肯定是 $O(\log n)$ 级别的。

​ 因为树的重链剖分显然是一组合法的好链划分，而轻边个数是 $\log n$ 条。

​ 现在考虑同时求出两问的答案。

​ 设 $f_{u,k,x}$ 表示：在 $u$ 的子树内作划分，和 $u$ 相连的好边有 $k$ 条，子树内最大答案为 $x$ 的方案数。根据题意，有 $k\in \{0,1,2\},x\le \log n$。设 $s_i$ 表示 $u$ 的儿子。有转移

$f_{u,0,x}=\sum_{\max\{y_i\}=x-1}\prod_{s_i}(f_{s_i,0,y_i}+f_{s_i,1,y_i}+f_{s_i,2,y_i})$

$f_{u,1,x}=\sum_{s_p\in\{s_i\}}\sum_{\max(\{y_i+1\},y_p)=x}(f_{s_p,0,y_p}+f_{s_p,1,y_p})\prod_{s_i}(f_{s_i,0,y_i}+f_{s_i,1,y_i}+f_{s_i,2,y_i})$

$f_{u,2,x}=\sum_{s_p,s_q\in\{s_i\}}\sum_{\max(\{y_i+1\},y_p,y_q)=x}(f_{s_p,0,y_p}+f_{s_p,1,y_p})(f_{s_q,0,y_q}+f_{s_q,1,y_q})\prod_{s_i}(f_{s_i,0,y_i}+f_{s_i,1,y_i}+f_{s_i,2,y_i})$

​ 一个树上背包的形式，类似于 “ 选取 $K$ 条不相交路径权值最大 ” 的套路。区别在于：和卷积换成了 max 卷积。

​ 最终最小值为最小的 $x$ 使得 $f_{1,k,x}$ 不为 $0$。

单次 max 卷积求解

​ 考虑如下问题：给定 $\{A_i\},\{B_i\}$，求

$F_n=\sum_{\max(i,j)=n}A_iB_j$

​ 方法是：先把 $A,B$ 进行前缀和变换，再进行点积（对应位置相乘），最后把得到的 $F$ 做差分变换。考虑这是为什么：前缀和后点积，所得的第 $n$ 项中会包含所有 $\max(i,j)\le n$ 的 $A_iB_j$ 之和，差分就是进行容斥。前缀和 / 差分变换在这里起到了 DFT 的作用，即，把卷积变为了点积运算。

树上背包

​ 现考虑把子树一个一个加进去。

​ 加入一个子树时，枚举它是否到当前节点有连边，发现可作如下转移：

$f_{u,0,x}\rightarrow f_{u,1,x},f_{u,1,x}\rightarrow f_{u,2,x},f_{u,0,x}\rightarrow f_{u,0,x},f_{u,1,x}\rightarrow f_{u,1,x},f_{u,2,x}\rightarrow f_{u,2,x}$

​ 顺着转移，每次作 max 卷积即可。

​ 总复杂度 $O(n\log n)$。

题外话

​ 有一个巨坑的点在于模数选取可能会正好使答案为 $0$，这个时候用 $f$ 一个数组无法找到最小值，解决方法是自己再找一个大模数先算一遍找到最小值再用原来的模数输出方案。后人切记后人切记后人切记