P4381 [IOI2008] Island 分析

__ryp__ · 2024-02-06 19:13:00 · 个人记录

本题就是在基环树上找直径。

我们可以先找出不带环时的直径。因为边权非负，我们可以用两次 DFS 或者树形 DP。

然后考虑带环的时候，直径会怎么变化。由于只有一个环，直径一定分为两个部分：树边组成的与环上的，设它们的交界点为 p 与 q，那么总直径长为 f(p) + f(q) + \sigma(p,q)。

但是，找这个最大值同样是无法接受的，这才是本题的难点。我们将环拆成两倍长度的链，于是问题转化成：在这个链上找 f(i) + f(j) + \sigma(i, j) 的最大值，\text{s.t.} \space \lvert j - i + 1\rvert \le n。

这可以用单调队列。以上。

好题！