RT，先给定一棵 $1$ 到 $n$ 的树，然后有以下转移式：

$dp_i= \max_{j<i} (dp_j+a_i\times b_{lca(i,j)})+c_i$

这个可以比较方便的优化到 $O(n\log_{2}n)$ 或 $O(n\log_{2}^2n)$ 吗/yiw