WC 2018 做题记录

迟到了一年的总结。

通道

来自猫锟的一道好（码农）题。著名的树上最优化直径乱搞题。

从部分分出发：

树 + 链：端点带权的直径，一样做。

树 + 树：利用两个点集并的直径端点一定是两个点集的端点。在一棵树上子树合并，将这棵树的 $\text{dep}$ 作为端点权值，维护每个子树中的点集的直径。合并时两两合并，更新答案的时候减掉 lca 的 $\text{dep}$ 。

树 + 树 + 树：一棵树上边分，将两个部分的点集到分治中心的距离也加入端点的权值，然后建立在第二棵树虚树和上面一样做。

代码实现因为有三棵树，所以最好把它用合理的方式分开。然后维护两个部分点集的时候，要分开维护直径。code

首先需要说明的 $p = 0, p = 1$ 的部分分。

它们分别对应有序和无序的方案（ $p = 1$ 表示无序证明：每个无序划分所有总排列贡献之和等于 $1$ ,计算时每次将依次将前两项、三项、四项相同的排列贡献合并）。

有序集合生成函数为 $F(x) = 1 + f(x) + f^2(x) + \ldots = \frac{1}{1 - f(x)}$ ；
无序集合生成函数为 $F(x) = 1 + \frac{f(x)}{1!} + \frac{f^2(x)}{2!} + \ldots = e^{f(x)}$ 。

带入子集卷积计算（外层 FMT，内层暴力求逆 / exp）。

接着考虑标算（和 $p$ 无关）：

转移式： $f_S = \sum_{T \subseteq S} [\text{T 合法}] f_{S-T} \left( \frac{sum_T}{sum_S}\right)^p$ 。

这有点像分治 FFT，然而子集卷积并不存在明显的分治对象。

但是我们可以直接使用子集卷积解法： $f_{i, S}$ 表示选了 $i$ 个元素，并集为 $S$ 的方案。然后外层 FMT，内层套卷积。我们只需要修改里面的卷积部分。

因为计算 $f_{i, S}$ 的时候只会利用 $j < i$ 的 $f_{j}$ ，所以完全可以将 $i$ 在外层枚举，然后 DP。

然后 $sum_S$ 那一部分放不进卷积（是个点积），这就只需要每一层计算完毕之后，IFMT 回来做点积，然后再 FMT 回去。所以常数有点大。code

容易从二叉树的部分分想到分治。

然后需要动态分治。

然后写个类似 ScapeGoatTree 的东西维护分治树，要重构的时候暴力 2-DFS 找重心重新分治。要找在哪一棵子树的时候，沿着 father 一直往上跳。

感觉递归版的替罪羊比以前写的迭代版要好些多了。。。code

另外还有 LCT 做法，好像是每次判断这个点在不在当前 splay 中，然后一直沿 splay 往下找，找到之后 access 一下。