BS8240
对于一条边连向的两个点，我们只关心他们颜色相同与否。于是可以考虑把 \(n\) 个点分成若干集合，每个集合内部颜色相同，集合之间没有区别。不难发现这就是贝尔数的定义。
注意到 \(bell_{12} = 4213597\)，于是当 \(n \leq 12\) 时直接搜索 \(n\) 个点的划分，再乘上 \(k^{\underline{cnt}}\) 即可。
再考虑一棵树的情况，容易设计 $dp_{x,i} $ 表示 \(x\) 颜色为 \(i\) 的总权值然后 \(O(nk)\) 转移，由于颜色之间没有区别，每个 \(i\) 的 \(dp_{x,i}\) 都是一样的，所以可以 \(O(n)\)。
于是就 70 了。
再考虑最后几个点，发现非树边最多只有 \(10\) 条，类似上面的思路，随便找一棵生成树后，对于每条非树边，直接搜索确定一点的颜色，此时设 \(dp_{x,i}\) 表示选择第 \(i\) 种颜色的方案（当 \(i = 0\) 时是未选择的 \(k - cnt\) 种颜色），最后把根据当前点的颜色选择，将其所对应的非树边答案累加。
于是复杂度就是 \(O(bell_{10}nk)\)，因为 \(bell_{10}\) 是 1e5 级别，算出来只有 1e8，但会被卡常。
题解的一个解决方案是将 1 度点删去，2 度点将其贡献累加到所连向的两个点。这样每个点度数 \(\geq 3\)，于是总点数减少，跑得飞快。
BS8241
建出括号树，对于一个询问 \(x, y(x<y)\) 而言，一定是不断跳，跳到其 lca 的两个儿子，要么直接从 lca 处转换括号，要么从同层括号之间单向移动。
于是只用预处理一个左 / 右括号到其父亲的 左 / 右括号的最小步数，显然可以在建树时用一个 \(2 \times 2\) 的矩阵表示转移。然后大力分讨就 over 了。
还有小清新的直接倍增写法，就是直接对每个点预处理跳 \(2^j\) 能到达的最左 / 最右点，一个跳 $2^j $ 的能到达的最左点要么是最靠左的 \(2^{j - 1}\)，要么是最靠右的 \(2^{j - 1}\)。询问类似上面的做法，从两个点开始跳，一直跳到 lca 即可。
BS8236
硬核推柿子题。
首先考虑求出一个点的期望深度，设 \(d_x\) 表示 \(x\) 的期望深度，\(b_x\) 为 \(a_x\) 的前缀和，有转移 \(d_x =\dfrac{\sum\limits_{i = 1}^{x - 1}a_i(d_i+c_i+c_x)}{b_{x - 1}}\)，可以通过分离变量做到 \(O(n)\)。
对于询问 \(x,y\)，我们想要对于每个 \(l \in [1, x]\)，计算出 \(l\) 为 \(x,y\) 的 \(\mathrm{lca}\) 的概率，答案就是 \(d_x+d_y -2\sum\limits_{l}P_ld_l\)。
假设 \(x<y\)，直接枚举 \(x - y\) 的路径上经过的点集 \(S_{x,y}\)，会发现其由两部分组成：在 \((l,x)\) 上的点可以在 \(l - x\) 的路径上，也可以在 \(l - y\) 上；对于 \((x,y)\) 的点，只能在 \(l - y\) 上，然后 开 幕 雷 击：
\(P_l =\dfrac{a_l^2}{b_{x - 1}b_{y - 1}} \sum\limits_{S_1 \subseteq (l, x)}\sum\limits_{S_2\subseteq (x,y)} \prod\limits_{i \in S_1}\dfrac{2a_i}{b_{i - 1}}\prod\limits_{i \in S_2} \dfrac{a_i}{b_{i - 1}}\)
解释一下：本质上就是一堆点，其 \(\dfrac{a_{p_{i - 1}}}{b_{p_i - 1}}\) 的乘积，只不过把 \(l, x, y\) 的贡献单独处理了，这个柿子在 \(x = l\) 时不成立，需要特殊处理。
然后将 \(\sum\limits_{S_1 \subseteq (l,x)}\prod ...\) 看成每个点选或不选：\(\prod\limits_{i = l+1}^{x - 1}(1+\dfrac{2a_i}{b_{i - 1}}) = \prod\limits_{i = l+1}^{x - 1}\dfrac{a_i+b_{i}}{b_{i-1}}\)，右边 \(\prod\limits_{i = x+1}^{y - 1}\dfrac{b_i}{b_{i - 1}} = \dfrac{b_{y - 1}}{b_x}\)。
最后的答案就是 \(d_x+d_y - 2\sum\limits_{l = 1}^{x}d_l \times \dfrac{a_l^2}{b_xb_{x - 1}}\prod\limits_{i = l+1}^{x - 1}\dfrac{a_i+b_{i - 1}}{b_{i - 1}}\)。预处理 \(\dfrac{a_i+b_{i - 1}}{b_{i - 1}}\) 的前缀积即可。
BS8237
题意就是划分成两个公差相同的等差数列（可以有一个为空），直观感受一下，这个公差不会太大。
为了方便确定公差的范围，我们不妨将公差 \(d\) 的上界和下界写出来，并枚举首项 \(b\)：
最少的操作次数 \(mn = \dfrac{\frac{n(n-1)}{2}d+bn - \sum a_i}{2}\)，\(mx = \dfrac{a_{mx} \times n - \sum a_i}{2}+2n\)，由于 \(mn \leq mx\)，最后发现 \(nd \leq 1e6\)。
这意味着我们可以直接暴力枚举 \(d \in [-\dfrac{lim}n, \dfrac {lim}n]\)，然后再花 \(O(n) - O(n \log n)\) 的时间得到让一段前缀 / 后缀变成公差为 \(d\) 的等差数列的答案，然后用 \(pre\) 和 \(suf\) 拼起来。
设 \(c_i = a_i - (i - 1) \times d\)，那么对于一个首项 \(b\)，对于 \(c_i - b \leq 0\) 的贡献而言，若 \(b - c_i\) 为偶数，就可以一直进行 +2 操作，次数就是 \(\dfrac{b - c_i}2\)，否则需要加到 1 后减去 1，贡献就是 \(\dfrac{b+3 - c_i}{2}\)；对于 \(c_i - b > 0\) 的贡献就是 \(c_i - b\)。
注意到这类似带权中位数问题，对于 \(c_i \leq b\)，贡献可近似看做 \(\dfrac{b - c_i}2\)，\(c_i > b\) 就是 \(c_i - b\)。根据数学？？积累可知：\(b\) 取 \(c[n - \left\lceil \frac n 3\right\rceil+1]\) 取到，由于奇偶性的问题，还需要代入该值 -1 检验。
考虑动态维护这个过程，我们需要动态维护前 \(n - \left\lceil \frac n 3\right\rceil+1\) 的奇 / 偶个数以及和，后 \(\left\lceil \frac n 3\right\rceil\) 的个数以及和就可以 \(O(1)\) 计算答案了。
用对顶堆时刻维护该过程，时间复杂度 \(O(nd \log n)\)。
标签：prod,limits,公差,dfrac,sum,leq,做题,寄录 From： https://www.cnblogs.com/henrici3106/p/16897411.html