题意

给定一棵带边权的无根树，要求删除一些边使得每个点的度数不超过 $k$，最小化费用，对所有 $[0,n-1]$ 中每个数回答询问。

其中 $2 \le n \le 250000$。

分析

首先，假如只有一个询问，记当前的最大度数为 $k$，设 $dp(x,0/1)$ 表示删除一些边使得 $x$ 点剩余度数为 $k$ 和 $k+1$ 的最小费用。转移时，不妨令所有边都没有被删除，将删除一条连向 $v$ 边权为 $w$ 的边产生的影响记录下来，即 $w+dp(v,1)-dp(v,0)$，如果是非负数直接选择，否则选择一些最小的。

回到原题，如何批量回答所有询问？

注意到一个事实：$\sum_{k=0}^{n-1} \sum_{u=1}^{n} [deg(u)>k]=2n-2$

考虑从小到大枚举最大度数 $k$，记度数大于 $k$ 的为关键点，否则为非关键点。

每个点维护一个堆，表示它删除所有连向非关键点的边的影响，因为非关键点度数小于等于 $k$，它的边随便删不删都行，因此这个影响等价于边权。

为了保证复杂度，每次只能 dfs 所有关键点构成的森林。因为非关键点的影响已经在堆内维护好了，只需要把关键点的影响丢进去即可，用类似与上述的方案求出相应的 $dp$ 值，注意出栈的时候，需要撤回一下关键点的操作。

树论

在算法竞赛中，树是一种应用广泛的抽象数据类型或者实现抽象数据类型的数据结构。

树结构可能会出现各种各样的题目中，作为解决问题算法或者问题本身。

线段树 / 树状数组维护 ······ 即可！

给一棵树，······，求 ······！

树论主要讨论在具体的一般树上的算法和问题。

min-max 容斥

证明

设容斥系数为 $f(|T|)$，则 $\max(S) = \sum_{T \subseteq S} f(|T|) \min(T)$。

考虑整体第 $k$ 小对最大值的贡献，显然当且仅当 $k=n$ 时，最小值有贡献，因此有下式：

组合意义为对于大于最小值 $n-k$ 个数，可以任意选取。枚举选了 $i$ 个数，再加上固定下来的第 $k$ 小，共 $i+1$ 个数，因此乘上容斥系数 $f(i+1)$。

变换一下，可得 $[ n = 0 ] =\sum_{i=0}^{n} { n \choose i } f(i+1)$。

套用二项式反演，可知 $f(n+1)=\sum_{i=0}^n (-1)^{n-i} { n \choose i } [ i = 0 ] $。

因此 $f(n+1)=(-1)^n$，即 $f(n)=(-1)^{n-1}$。

题意

给定一棵带边权 $\{ 0, 1\}$ 的无根树，求回文路径的个数。

其中 $3 \le n \le 5\times 10^4$。

分析

点分治，问题转化为求有多少条过当前重心的路径，使得其构成回文串。

将从重心开始的所有结点对应的串，插入 Trie 树中，最坏情况下 Trie 树与原树同构。

分析跨越重心 $root$ 路径的回文串结构，记两个端点分别为 $u,v$，其中 $u$ 的深度大于等于 $v$ 的深度。

深度相同，则 $root$ 到 $u$ 路径对应串 (简记为 $u$ 串) 必须等于 $root$ 到 $v$ 路径对应串 (简记为 $v$ 串)。令枚举的每个结点的出现次数为 $cnt$，这部分答案贡献为 $cnt \choose 2$。

深度不同，则 $v$ 串等于 $u$ 串的后缀，且 $u$ 串的前缀是一个回文串。

因此，我们考虑对 Trie 树构建 AC 自动机，则 $u$ 串的所有在 Trie 树中有对应结点的后缀就是 fail 树上的所有祖先。注意到，fail 树上的祖先可能很多，无法枚举并检查当前前缀是否为回文串。但是，根据 $Border$ 理论，一个串的回文后缀（前缀）可以表示为 $\log n$ 段等差数列。于是，我们处理所有 Trie 树结点的等差数列 $(l,r,d)$，对应表示首项、末项和公差。这可以在构建完 Trie 树后，dfs Trie 树，并维护正串和反串的哈希值得到。

最后，枚举所有 Trie 树结点，令其深度为 $len$，再枚举其等差数列，只需要询问 fail 树的祖先上长度为等差数列 $(len-r,len-l,d)$ 的出现次数和，进一步转化可以变成求所有长度 $l \equiv ((len-l) \bmod d) ( \bmod d)$ 的点值和，考虑根号分块容易维护，但是可能会取到一些等差数列值域外的点，可以将询问离线的最大长度上，并拆成两个前缀和，在 dfs fail 树的栈上二分即可获得对应结点。

总结

1. 点分治。

2. 插入从重心开始的 Trie 树。

3. dfs Trie 树，求出每个点回文前缀的等差数列。

4. dfs fail 树，维护栈上的结点，维护栈上支持快速查询模 $b$ 余 $r$ 处点值的分块数据结构。枚举等差数列，对于公差小的，栈上二分找到询问离线点，对于公差大的，暴力枚举。

5. 枚举 Trie 树结点，计算回文前缀为空和不为空的匹配方案数。

6. 点分治容斥掉来自同一子树的配对答案数。

时间复杂度：$T(n)=2T({n \over 2})+O(n \sqrt{n}+n\log^2 n)$，$T(n)=O(n \sqrt{n})$。

E Marbles

给定一个序列，每次交换两个相邻位置，求使得数组中所有相同颜色都是连续段的最少操作次数。

颜色种数只有 $20$，注意到数组最后形态会有 $20!$ 种。

可以从左到右确定，记 $dp(mask)$ 表示左边已经确定了集合 $mask$ 的最小操作数。

转移时，枚举一个没有固定颜色，将其接在后面，因为前面的操作不会改变其他颜色的相对关系，因此操作次数等价于该颜色和其他未出现在集合的颜色的逆序对数。