https://cplusoj.com/d/master/contest/6a119af6a9d60f6c5f299677/
T1 序列(seq)
T2 夕阳(sunset)
建出小根笛卡尔树。
\(f(1)\)：计算 \(\max_u h_u\times len_u\)。
\(f(2)\)：可能叠起来或者是分开的。
可以选择：
- 继承两个儿子中 \(\max (f_L(2),f_R(2))\)。
- 分别从两个儿子中选择一个矩形：\(f_L(1)+f_R(1)\)。
- 选择这个节点和某个子树节点，那么贡献是 \(h_u\times len_u+f_{v}(1)-h_u\times len_v\)，可以维护李超合并。
\(f(3)\)：类似的，可以选择：
- \(\max (f_{L}(3),f_R(3))\)。
- \(f_L(1)+f_R(2),f_{L}(2)+f_{R}(1)\)。
- \(h_u\times len_u+f_v(2)-h_u\times len_v\)。
- \(s_u+s_a+s_b-h_u\times (len_a+len_b)\)，\(a,b\) 是子树内没有祖先后代关系的一对点。
只有最后一种情况不好处理。放宽限制，\(u\) 可以取所有点。
那么每个点就是有 \(s_a-len_a\times x\) 这条直线。
把子树变成区间 \([l_1,r_1],[l_2,r_2]\)，那么考虑线段树，在线段树节点 \(LCA(r_1,l_2)\) 处统计这个点对。
每个线段树节点维护两个凸包 \(L,R\)。
对于子树 \([l,r]\)，在 \(l\) 的祖先 \(L\) 凸包内插入直线，在 \(r\) 的所有祖先 \(R\) 凸包内插入直线。
最后每个线段树节点求完凸包后计算 \(L,R\) 的闵和。最后得到的所有点集都插入新凸包。
那么 \(u\) 在凸包上二分做查询即可。