本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-04 11:33:09

本题虽然是在树上的操作，但是实际上是区间 DP 的典题。

我们知道：在中序遍历中，一个点左边的序列和右边的序列就是其左子树和右子树。因此，我们的问题就转化为了求区间中的最优分割点 $k$，使 $\sigma_{l,k-1} \times \sigma_{k+1,r} + \sigma_{k,k}$ 最大。

之后的问题就是找到先序遍历。这实际上也是很简单的。我们将每一个区间的最优分割点保存下来，于是这个点就是这个区间所建的树的根。之后打印即可。

总之，对于中序遍历的问题，我们可以转化为区间上的问题。