以 $1$ 为根，求出每个点的深度 $d_i=\mathrm{dist}(1,i)$，记 $i$ 左边第一个比 $i$ 深的点是 $\mathrm{pre}(i)$，右边第一个比 $i$ 深的点是 $\mathrm{suf}(i)$。

记 $L_i=\mathrm{dist}(i,\mathrm{suf}(i))-d_{\mathrm{suf}(i)},R_i=\mathrm{dist}(\mathrm{pre}(i),i)-d_{\mathrm{pre}(i)}$，求出如上信息的总代价为 $3n$。

那么记 $[l,r]$ 中最深的点是 $u$，那么 $f(l,r)=d_u+max(L_l\sim L_{u-1},R_{u+1}\sim R_r)$，证明如下：

首先我们可以通过调整法证明区间直径一定经过 $u$，否则把其中一个端点换成 $u$ 肯定不劣。

考虑每个 $L_x$ 对答案的贡献：

• 若 $\mathrm{suf}(x)=u$，那么 $L_x=d_x-2d_{\mathrm{LCA}(x,u)}$，那么 $L_x+d_u=\mathrm{dist}(u,x)$。
• 若 $\mathrm{suf}(\mathrm{suf}(x))=u$，那么只要考虑 $L_x>L_{\mathrm{suf}(\mathrm{x})}$ 的情形，否则 $x$ 必定无贡献，由于 $d_x\le d_{\mathrm{suf}(x)}$，因此 $d_{\mathrm{LCA}(x,\mathrm{suf}(x))}<d_{\mathrm{LCA}(\mathrm{suf}(x),u)}$，所以 $\mathrm{LCA}(x,\mathrm{suf}(x))$ 是 $\mathrm{LCA}(\mathrm{suf}(x),u)$ 的祖先，因此 $\mathrm{LCA}(x,\mathrm{suf}(x))=\mathrm{LCA}(x,u)$。

所以只要 $L_x>L_{\mathrm{suf}(x)}$，$\mathrm{LCA}(x,\mathrm{suf}(x))=\mathrm{LCA}(x,\mathrm{suf}(\mathrm{suf}(x)))$，数学归纳法可以证明最大的 $x$ 满足 $\mathrm{LCA}(x,\mathrm{suf}(x))=\mathrm{LCA}(x,u)$。

证毕。

那么原问题就转化成了一个数据结构问题，自然的想法是考虑对 $d$ 建立大根笛卡尔树。

设当前节点为 $p$，子树区间为 $[l,r]$，$d_p$ 的贡献就是 $(r-p+1)\times (p-l+1)-1$。

我们只要求 $\sum _{l\le i\le p}\sum _{p\le j\le r}max(L_i\sim L_{p-1},R_{p+1}\sim R_j)$。

假如 $p$ 是区间中点，那么这是经典的，枚举 $i$，双指针求 $j^{\ast }$ 为最后一个满足 $max(R_{p+1}\sim R_j)\le max(L_i\sim L_{p-1})$ 的 $j$。

那么 $max(L_i\sim L_{p-1})$ 的贡献就是 $j^{\ast }-p+1$，而 $\sum _{j^{\ast }<j\le r}max(R_{p+1}\sim R_j)$ 可以简单后缀和。

但是此时 $p$ 不一定是区间中点，如果处理复杂度是 $\mathcal{O}(r-l)$ 的话会退化到 $\mathcal{O}(n^2)$，但是如果可以做到 $\mathcal{O}(min(p-l,r-p))$ 的话，相当于每次遍历笛卡尔树上的轻子树，复杂度显然是 $\mathcal{O}(n\log n)$。

不妨假设 $p-l\le r-p$，我们依然枚举每个 $i$，那么 $j^{\ast }$ 可以二分求出，$max(L_i\sim L_{p-1})$ 贡献依然是简单计算的。

而 $\sum _{j^{\ast }<j\le r}max(R_{p+1}\sim R_j)$ 可以拆成 $\sum _{p<j\le r}max(R_{p+1}\sim R_j)-\sum _{p<j\le j^{\ast }}max(R_{p+1}\sim R_j)$。

那么问题就变成了 $\mathcal{O}(n\log n)$ 次询问 $fr(x,y)=\sum _{x\le i\le y}max(R_x\sim R_i)$。

离线这些问题后可以扫描线，单调栈+区修区查树状数组维护前缀最大值，可以 $\mathcal{O}(n{\log }^{2}n)$ 求出答案。

询问次数 $3n$，时间复杂度 $\mathcal{O}(n{\log }^{2}n)$。

Submission Link