CF932F Escape Through Leaf
Codeforces Luogu 分析 容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。...
Codeforces Luogu 分析 容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。...