决定以后分开写，显的博客多。

A：

首先考虑对给定树计算权值，假设我们已经知道了一个权值最小的划分，那么可以通过调整得到新的划分使得权值不变，目的是简化虚树的形态。

考虑该划分中任意一个集合形成的虚树，有两种情况：如果根节点 $r$ 存在于任何一个最大独立集中，即 $f_{r,1}>f_{r,0}$，则不存在 $r$ 的儿子 $v$ 使得 $f_{v,0} < f_{v,1}$。

此时，将该虚树中的点按照 $r$ 的不同子树分成多个集合，并将 $r$ 任意放入一个集合（如果 $r$ 不是虚点），则权值一定不会增大；

反之，若 $f_{r,1}\leq f_{r,0}$，则存在 $v$ 使得 $f_{v,0}< f_{v,1}$。此时，将虚树中的点按照 $r$ 的子树分开，将 $r$ 归入子树 $v$，权值也不会增大。

根据以上思路，我们可以归纳地证明，权值最小的划分一定只由两种结构组成：一个孤点，或者一个有祖先后代关系的点对。

我们已经证明了可以将 $r$ 的所有子树分开，而不会增大权值。由归纳假设，$r$ 的所有子树都可以调整为只由孤点和点对组成的划分，如果其中存在孤点，我们将其与 $r$ 匹配为点对，否则将 $r$ 作为孤点，容易得到，这样依然不会增大权值。

因为孤点和点对的权值都是 $1$，所以权值最小的划分就是要最大化选出的点对数。

考虑 dp，记 $g_u$ 表示 $u$ 的子树内最优的划分会剩下多少个孤点。如果 $\sum_v g_v>0$，则让 $u$ 与一个孤点匹配，即 $g_u=\sum_v g_v - 1$，否则 $g_u=1$。最终答案为 $\frac{n+g_0}{2}$。

对于加点，可以考虑类似 DDP 的做法，树剖后，可以求出轻子树的 $\sum g_v$，我们需要维护函数 $h(x)$ 表示当重儿子 $g_s=x$ 时 $g_u$ 的值，$h(x)$ 是一个分段函数，存在分界点 $p$，满足 $x\leq p$ 时 $h(x)=a\left(x\wedge1\right)+b$（$\left(x\wedge1\right)$ 表示 $x$ 的奇偶性），$x>p$ 时 $h(x)=x+c$。

因此，$h(x)$ 是可合并的，支持快速复合，可以用线段树维护，套用 DDP 的做法。

B：

设 $k$ 为区间长度，考虑置换环，$p$ 进行一次置换相当于每个位置变为置换环上的下一个位置，终止条件为 $[l,r]$ 对应 $p$ 的值域也为 $[l,r]$。

考虑到满足条件的排列每次置换完后区间 $[l,r]$ 仍为一个值域连续段，内部可以自由排列，其贡献为：

$$\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}(k!)^{i} \cdot(i-1)!\cdot(n-i k)!\cdot F_{i, l-1, n-r, k}$$

其中：

$$F_{i, x, y, k}=\sum_{j=0}^{i-1}\binom{x-j(k-1)}{j}\binom{y-(i-j-1)(k-1)}{i-j-1}$$

对于所选中区间相交的情况有结论：“如果将所有相交的区间合并成一个连续段，则每一个连续段有且仅有两个区间，且所有连续段长度相同。在通过置换环向后跳的过程中，会首先依次经过每个连续段中的一个区间，再按相同的顺序经过每个连续段中的另一个区间，最后回到初始区间。”

若一个连续段是由 $[l_1,r_1]$ 与区间 $[l_2,r_2]$ 构成，不妨设 $l_1<l_2$ ，若左区间最小值小于右区间最小值，则称该连续段是上升的，否则为下降的。

假设一共形成了 $m$ 个连续段，这些连续段的指向关系会构成一个圆排列，其中下降段的个数一定为奇数。

不妨设 $[l,r]$ 连续段为上升的，则该部分贡献为：

$$\sum_{d=1}^{k-1} \sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor} 2^{i-1} \cdot\left((k-d)!^{2} \cdot d!\right)^{i} \cdot(i-1)!\cdot(n-i(2 k-d))!\cdot F_{i, l-1, n-r-k+d, 2 k-d}$$

后边的 $F$ 可以用 NTT 计算，总时间复杂度为 $\mathcal{O}(n\log n)$。

C：

爱谁改谁改

---

下午把键盘拆开擦了一遍，国庆放假时机房换灯掉下来的墙皮全掉键盘缝里了，擦完舒服多了。

怎么会有人能做到用了两个月的新键盘 键帽比我用了大半年的还油的。

最近有点神金事整的我挺烦的。