自动搬运

查看原文

来自洛谷，原作者为

	H6_6Q qwq

搬运于2025-08-24 22:29:07，当前版本为作者最后更新于2021-02-15 21:36:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\large\text{Solution}$

简单说下我的做法吧。

对于树上的每一条链，我们可以通过维护一些信息来使得两条链之间可以合并。

那么一个显然的思路是维护：

1. 该链的两端都不开船的最小花费 $a$

2. 该链的下端开船，上端不开船的最小花费 $b$

3. 该链的上端开船，下端不开船的最小花费 $c$

4. 该链的两端都开船的最小花费 $d$

那么显然最简单的情况也就是只有一条边的情况，我们以此为边界。

然后就是考虑如何合并两条链 $x,y$ 的信息，使得合并后 $x$ 在下 $y$ 在上。

设合并完的链为 $z$，那么显然有以下式子：

既然已经支持合并，那么可以直接倍增瞎搞了。

当然还有很多细节要处理，不过都是一些小问题了。

代码就不放了，写得太丑了（