题解 P7359 【旅行】

· · 题解

\large\text{Solution}

简单说下我的做法吧。

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

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

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

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

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

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

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

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

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

a_z=\min(a_x+a_y,a_x+b_y,c_x+a_y,c_x+b_y-L) b_z=\min(b_x+a_y,b_x+b_y,d_x+b_y-L,d_x+a_y) c_z=\min(c_x+c_y,c_x+d_y-L,a_x+c_y,a_x+d_y) d_z=\min(d_x+d_y-L,d_x+c_y,b_x+c_y,b_x+d_y)

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

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

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