决定以后分开写，显的博客多。
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}\)。
对于加点，可以考虑类似动态 dp 的做法，树剖后，可以求出轻子树的 \(\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)\) 是可合并的，支持快速复合，可以用线段树维护，套用动态 dp 的做法，时间复杂度 \(\mathcal{O}\left(n\log^2 n\right)\) 或 \(\mathcal{O}\left(n\log n\right)\)。
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} \]对于所选中区间相交的情况有结论：“如果将所有相交的区间合并成一个连续段，则每一个连续段有且仅有两个区间，且所有连续段长度相同。在通过置换环向后跳的过程中，会首先依次经过每个连续段中的一个区间，再按相同的顺序经过每个连续段中的另一个区间，最后回到初始区间。”
C：
爱谁改谁改
