哈哈写总结最早一天。改不动根本改不动。
NOIp 模拟赛放三道神秘题不知道出题人是不是考过这种 NOIp 哈哈。
A
根据猜结论（并通过大样例验证）可以得到划分的每组点要么是祖先-后代点对，要么是孤点。每组代价是 \(1\)。
然后简单 dp 是设 \(f_x\) 表示 \(x\) 子树内最少的孤点。
\[f_x= \begin{cases} (\sum_{y\in son} f_y) - 1 & (\sum_{y \in son} f_y \neq 0)\\ 1 & \operatorname{otherwise} \end{cases} \]答案为 \(\left\lfloor\dfrac{i + 1 - f_0}{2}\right\rfloor + f_0\)。
然后场上 \(O(n^2)\) 写挂。
然后考虑类似 DDP 写法。
每个点维护轻子树传上来的贡献，考虑一条重链上怎么匹配：
上部的链上点可以匹配下部的点，考虑先用上部链上点匹配下部轻子树内点，最后链上点可以两两匹配。
更新完一条链记得更新链顶父亲。
B
讲评：
题解直接把结论摆上来了啊。
怎么证？我也不会。我建议你们直接把式子抄上 NTT。
如果排列 \(p\) 在区间 \([l,r]\) 上是值域连续段，那么该区间做一次置换后也是一个区间。因为 \(p\) 做任意次置换后 \([l,r]\) 都是值域连续段。
如果这些区间互不相交，则在置换环上，这些区间构成一个圆排列。每一段区间都是值域连续段，在确定该区间跳到的区间后，它的值域也确定了，并且内部可以任意排列。因此这部分对答案的贡献是：
\[\sum_{i=1}^{\left\lfloor \frac{n}{k}\right\rfloor} (k!)^i\cdot (i-1)!\cdot (n - ik)! \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} \]可以 NTT 计算。
对于相交的情况，有结论：如果将所有相交的区间合并成一个连续段，则每一个连续段有且仅有两个区间，且所有连续段长度相同。在通过置换环向后跳的过程中，会首先依次经过每个连续段中的一个区间，再按相同的顺序经过每个连续段中的另一个区间，最后回到初始区间。
若一个连续段是区间 \([l_1,r_1]\) 与区间 \([l_2,r_2]\) 构成的，设 \(l_1 < l_2\)，若区间 \([l_1,r_1]\) 中的最小值小于区间 \([l_2,r_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 \left(n-i(2k-d)\right)!\cdot F_{i,l-1,n-r-k+d,2k-d} \] 标签：right,cdot,sum,09,24.10,连续,区间,left From： https://www.cnblogs.com/KinNa-Sky/p/18454626