Shik

一道有意思的 $\text{dp}$ 呀。 ### 思路 我们容易发现，一个点最多会往回走一次。 也就是每一个点最多被遍历三次。 因此，我们可以考虑每个点的贡献。 $$dp_i=\min_{j=1}^{i-1}dp_j+x_i-x_j+\max(2\times(x_i-x_{j+1}),T)$$ 其 ......

不难的题，但是突然就不会分析复杂度了！脑子出了些什么问题。 首先考虑题目中要求一条边恰好经过两次，那么也就是说每进入一个子树，那么就必须把子树内的所有点探索完后再去另一个子树，那么这个问题就显然是可以递归处理的了。 具体来说，对于每一个子树 $u$，都存在若条路径 $u \to v$，然后当子树合并 ......