本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$。

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

好题！