icetea sol2
sol1省流:建立线段树,在每一个节点上维护\(f_u(x)\)表示父节点冰红茶有\(x\)个单位,\(u\)的子树内所有边权值和加上\(u\)到父亲边权的最小值.这样根节点两个子节点的\(f\)之和的最小值即为答案.\(f\)的合并方式不再叙述.
为了方便表述,我们记线段树上节点\(u\)的子树内\(\sum h\)记为\(sum_u\),左子节点为\(ls_u\),右子节点为\(rs_u\),其管辖区间为\([l_u,r_u]\),管辖区间长度\(len_u=r_u-l_u+1\).
结论:
\[ans=\sum_{u\text{不为叶节点}}len_u(len_u-1)(sum_{ls_u}-sum_{rs_u})^2 \]通过这个结论我们可以支持区间加减
证明:
我们基于sol1,研究每一个节点上\(f\)的性质.
我们发现:
对于一个非叶节点\(u\),设\(f_{ls_u}(x)+f_{rs_u}(x)=ax^2+bx+c\),则有如下结论成立:
(记\(f_u(x)\)的三个系数分别为\(a_u,b_u,c_u\))
对于节点\(u\),我们有:
\[a_u=\frac{len_u}{2len_u-1} \\ b_u=\frac{2}{2len_u-1}sum_u \\ c_u=-\sum_{v\in \operatorname{subtree}(u),\text{v不是叶子}}\frac{sum^2_v}{(2len_v-1)(len_v-1)}+\sum_{i=l_u}^{r_u}h_i^2 \]具体过程
\[a = a_l+a_r \\ b = b_l+b_r \\ c = c_l+c_r \\ a_u = \frac{a}{a+1} \\ b_u = \frac{b}{a + 1} \\ c_u = c - \frac{b ^ 2}{4a} \]我们发现,叶子节点处\(f(x)=(x-h)^2,a=1\).
而父节点的\(a\)只依赖子节点\(a\),则\(a\)的值只会与层数有关,与\(h\)无关.这样,我们设\(a_i\)表示自底向上的第\(i\)层的\(a\)值,则有
\[a_i=\frac{2a_{i-1}}{2a_{i-1}+1} \]根据高中数列知识可得,\(a_i=\frac{2^{i-1}}{2^i-1}\).
一种可能的证明
\[a_i=\frac{2a_{i-1}}{2a_{i-1}+1}\\ 2a_ia_{i-1}+a_i=2a_{i-1}\\ 2a_{i-1}(2a_i-1)=a_i(2a_{i-1}-1)\\ \frac{a_i}{2a_i-1}=2\frac{a_{i-1}}{2a_{i-1}-1} \]由于\(a_1=1,\frac{a_1}{2a_1-1}=1\),那么
\[\frac{a_i}{2a_i-1}=2^{i-1} \\ a_i=\frac{2^{i-1}}{2^i-1} \]经过类似的证明与观察,我们能得到:
我们发现,每个节点的\(-\frac{sum^2_u}{(2len_u-1)(len_u-1)}\)都会给其父链上的点的\(c\)贡献.因此我们可以写出通项公式
\[c_u=-\sum_{v\in \operatorname{subtree}(u),v\text{不是叶子}}\frac{sum^2_v}{(2len_v-1)(len_v-1)}+\sum_{i=l_u}^{r_u}h_i^2 \]有了上面的公式,我们就可以通过\(h\)直接表示出\(ans\)了.
\[ans=\min(f_{ls_{root}}+f_{rs_{root}}) \]这个二次函数参数:
\[a = \frac{n}{n-1}\\ b = \frac{2}{n-1}\sum_{i=1}^n h \\ c = -\sum_{v\in \operatorname{subtree}(root) / \{root\},v\text{不是叶子}}\frac{sum^2_v}{(2len_v-1)(len_v-1)}+\sum_{i=1}^n h^2 \]根据初中二次函数知识,有:
\[ans = \frac{4ac-b^2}{4a}=\sum_{i=1}^n h^2-\sum_{v\in \operatorname{subtree}(root) / \{root\},v\text{不是叶子}}\frac{sum^2_v}{(2len_v-1)(len_v-1)}-\frac{(\sum_{i=1}^n h)^2}{n(n-1)} \]这个式子看起来缭乱不堪,但是我们其实只需要关心每一项的系数即可,后面再慢慢化简.
sol2的式子:
\[ans=\sum_{u\text{不为叶节点}}len_u(len_u-1)(sum_{ls_u}-sum_{rs_u})^2 \]比对系数:
平方项
为方便,下面的求和式的i均为2的整数次幂
对于\(h_i^2\),在sol1中它的系数为:
\[1-\sum_{i=2,4,8,\dots}^{n/2}\frac{1}{(i-1)(2i-1)}-\frac{1}{n(n-1)} \]在sol2中它的系数为:
\[\sum_{i=2,4,8,\dots}^{n}\frac{1}{i(i-1)} \]通过简单化简与高中数列知识,可以证明他们是相等的.
一种可能的证明
\[\begin{align} & 1-\sum_{i=2,4,8,\dots}^{n/2}\frac{1}{(i-1)(2i-1)}-\frac{1}{n(n-1)}=\sum_{i=2,4,8,\dots}^{n}\frac{1}{i(i-1)}\notag \\ \Leftarrow & \sum_{i=2,4,8,\dots}^n\frac{3i-1}{i(i-1)(2i-1)}=\frac{n(2n-1)-1}{n(2n-1)} \notag \\ \Leftarrow & \sum_{i=2,4,8,\dots}^n(\frac{3i-1}{i(i-1)(2i-1)}+\frac{1}{i})=\frac{n(2n-1)-1}{n(2n-1)}+\frac{n-1}{n} \notag \\ \Leftarrow & \sum_{i=2,4,8,\dots}^n\frac{i}{(2i-1)(i-1)}=\frac{2n-2}{2n-1} \notag \\ \Leftarrow & \sum_{i=2,4,8,\dots}^n(\frac{2i-2}{2i-1}-\frac{i-2}{i-1})=\frac{2n-2}{2n-1} \notag \\ \Leftarrow & \frac{2n-2}{2n-1}-0=\frac{2n-2}{2n-1} \text{ 显然成立}\notag \\ \end{align} \]于是两者系数一致.
交叉项
对于一组\(i,j(i\neq j)\),考虑\(h_ih_j\)在sol1中的系数,发现与lca有关,我们设他们的lca节点长度为\(k\).
则有sol1的系数为
\[-\sum_{i=k,2k,4k,\dots}^{n/2}\frac{2}{(i-1)(2i-1)}-\frac{2}{n(n-1)} \]sol2的系数为
\[-\frac{2}{k(k-1)}+\sum_{i=2k,4k,\dots}^n\frac{2}{i(i-1)} \]通过类似的过程,能够证明二者一致.
一种可能的证明
\[\begin{align} & -\sum_{k,2k,\dots}^{n/2}\frac{2}{(i-1)(2i-1)}-\frac{2}{n(n-1)}=-\frac{2}{k(k-1)}+\sum_{i=2k,4k,\dots}^n\frac{2}{i(i-1)} \notag \\ \Leftarrow & -\sum_{k,2k,\dots}^{n}\frac{1}{(i-1)(2i-1)}+\frac{1}{(n-1)(2n-1)}-\frac{1}{n(n-1)}=-\frac{2}{k(k-1)}+\sum_{i=k,2k,\dots}^n\frac{1}{i(i-1)}\notag \\ \Leftarrow & \sum_{k,2k,\dots}^{n}\frac{3i-1}{i(i-1)(2i-1)}=\frac{2}{k(k-1)}+\frac{1}{n(1-2n)}\notag \\ \Leftarrow & \sum_{k,2k,\dots}^{n}(\frac{3i-1}{i(i-1)(2i-1)}+\frac{1}{i})=\frac{2}{k(k-1)}+\frac{1}{n(1-2n)}+\frac{n-1}{n}-\frac{k-2}{k}\notag \\ \Leftarrow & \sum_{k,2k,\dots}^{n}(\frac{2i-3}{2i-1}+\frac{i-3}{i-1})=\frac{2n-3}{2n-1}-\frac{k-3}{k-1}\text{ 显然成立 } \notag \end{align} \]于是两者系数一致.
综上,通过比对各项系数,sol1与sol2所得式子完全一样,sol2得证.
标签：dots,frac,sum,节点,icetea,2n,sol2,2i From： https://www.cnblogs.com/snowycat1234/p/18399032