CF1303G Sum of Prefix Sums

题意：给出一棵 个节点的树，点有点权，均为正。

定义树上有向路径 的权值为：其点权的前缀和的和。

求权值最大的有向路径。

，时限 。

---

考虑点分治。思考如何合并两条路径。

用 表示一条和为 ，长为 ，权值为 的路径。

那么 合并之后的路径权值为 。

不难发现，若枚举 ，可以把 的贡献看作 的一次函数。

贡献必须来自不同的分支。经典地，将分支按某种顺序排序，用数据结构维护前缀分支的候选半路径，对于每个分支，先尝试和之前分支的半路径拼接，再将其加入数据结构。这样可避免同分支内的贡献。本题路径有向，需要正反各做一次。

这需要维护一次函数集合 ，支持插入一次函数，给定 求最大函数值。

李超树即可。

复杂度 。