<h2>A.珂学家</h2>
<h3>题解</h3>
如果 $l,r$ 的范围不大的话，我们记 $S$ 表示将每个区间的权值都加在区间上后得到的序列，$A_i$ 表示第 $i$ 个区间区间加后得到的序列。我们考虑预处理：答案多项式$$Ans = S^2 - \sum_{i=1}^n A_i^2$$
前面可以 NTT，后面发现是一些区间加等差数列，两次差分即可。
想到了加等差数列，又发现 $n$ 特别小，我们可以考虑枚举每一对区间计算它们的贡献发现他们的贡献是一个等差数列的形式，直接两次差分后单点加即可。
代码
<h2>B.B</h2>
<h3>题目大意</h3>
一棵树，如果一个点有父亲的父亲，还要在这个点和它父亲的父亲的点连边。
随机游走，求每个点到达根节点的期望步数。
<h3>题解</h3>
树上高斯消元模板题。。在这里记录一下就好了。
设 $f_v$ 表示 $v$ 走到根的代价，转移十分显然：
$$f_v = \frac{\sum_{to} f_{to}}{deg} + 1$$
一般树上高斯消元需要将 $f_v$ 用它上面的点的线性组合来表示，由于根的上面没有点，就可以得到根的答案，进而求出所有点的答案。
令 $fa_v^x$ $v$ 的 $x$ 级祖先，这一题里我们可以令 $f_i = Af_{fa_i^2}+Bf_{fa_i}+C$，然后我们目标是将其转化成一个只与上面的点有关的式子：
这里令 $son_v$ 表示 $v$ 的儿子集合，$sson_v$ 表示通过新加的边连接这个点和它先面的点的集合。$v$ 简略不写
begin{align}
degf_v &= sum_{x in son}f_x+f_{fa_v}+f_{fa_v^2}+sum_{x in sson} f_x \\
&= sum_{xin son} (A_x f_{fa_v}+B_xf_v+C_x) + f_{fa_v} + f_{fa_v^2} + sum_{x in sson} (A_xf_v + B_xf_{fa_x}+C_x) \
&= sum_{xin son} (A_x f_{fa_v}+B_xf_v+C_x) + f_{fa_v} + f_{fa_v^2} + sum_{x in sson} (A_xf_v + B_x(A_{fa_{x}}f_{fa_v}+B_{fa_x}f_{v}+C_{fa_x})+C_x) \\
&text{经过简单整理可以得到} \\
f_v &= frac{f_{fa_v^2} + (sum_{x in son}A_x + sum_{x in sson}B_x*A_{f_x}+1)f_{fa_v}+(sum_{x in sson} C_x + sum_{x in son} C_x + sum_{x in sson} B_xC_{f_x})}{deg-sum_{xin son}B_x - sum_{x in sson} A_{f_x} - sum_{x in sson} B_xB_{fa_x}}
end{align}
直接 dfs 处理就好了。
代码
<h2>C.C</h2>
<h3>题解</h3>
首先我们可以得到一个方程：
$$\sum_{i=1}^m \frac{w_i}{\sum w}|i-d| = d$$
这种是怎么得到的呢？首先我们考虑 |i-d| 的实际意义：如果 $i < d$ 那么实际上就是 $d-i$，也就是这次操作失去了 $i$ ，但还是将决定权保留在手中 ($d$)，反之亦然。然后两边的期望是相等的。
所以我们实际就是要解方程（外加修改）
设 $S = \sum w$，令 $f(d) = \sum_{i=1}^m w_i|i-d| - Sd$，显然我们是要求使 $f(d) = 0$ 的 $d$，我们可以考虑如果确定了 $d$ 的整数部分，那么绝对值就可以消去了，进而可以通过解方程获得答案。
考虑 $f(d)$ 其实是单调减的（因为 $\sum_{i=1}^m w_i|i-d|$ 比 $Sd$ 的变化量要小），所以我们就可以二分，要找到第一个位置使得 $f(d) > 0$,$f(d+1) < 0$假设我们现在二分到了 $d$，拆一下式子：
$$f(d) = \sum_{i=1}^d w_i* i - d\sum_{i=1}^dw_i + d\sum_{i=d+1}^n w_i - \sum_{i=d+1}^n i * w_i - Sd$$
记 $g(d) = \sum_{i=1}^d w_i,h(d) = \sum_{i=1}^d w_i * i$，式子可以进一步简化为：
$$f(d) = h(d)-dg(d)+(d(g(n)-g(d)))-(h(n)-h(d))-Sd$$
只需要进行单点修改 维护前缀和就可以了，树状数组就可以。
代码
