CF1303G Solution
\(k\) 个数 \(a_i\) 的前缀和的和就是 \(\displaystyle\sum_{i=1}^k(k-i+1)a_i\)。
这个题可以考虑换一下 \(u,v\)，那么式子就变成了 \(\displaystyle\sum_{i=1}^kia_i\)。
注意到要统计树上路径的最值，考虑点分治。
考虑上面的式子从 \(j\) 处断开，那么式子变成
\[\sum_{i=1}^jia_i+j\sum_{i=j+1}^ka_i+\sum_{i=j+1}^k(i-j)a_i \]那么这里 \(j\) 就对应点分治向下搜路径时的路径长度。
对于第一个部分我们可以边搜边处理。
第二，三个部分，我们把第二部分 \(j\) 后面的和当作斜率，第三部分当作截距，在李超树中查询最大值即可。
复杂度 \(\mathcal O(n\log^2n)\)。
标签：sum,路径,solution,cf1303g,displaystyle,式子 From： https://www.cnblogs.com/iorit/p/18040096