形式化题意
给定一棵由 \(n~(1 \leq n \leq 2 \times 10^5)\) 个结点组成的无根树，设 \(f(r, u, v)\) 代表以 \(r\) 作为根结点时，\(u\) 结点与 \(v\) 结点的 LCA（最近公共祖先）的结点编号，求：
\[\sum_{r=1}^{n} \sum_{u=1}^{n} \sum_{v=u}^{n} f(r, u, v)
\]
解题报告
首先显然可以直接转化成贡献形式，即
\[\sum_{i=1}^{n} i \times cnt_{[f(r,u,v)=i]}
\]
直接考虑求 \(cnt_{[f(r,u,v)=i]}\)。考虑去掉点 \(i\)，树会变成一些连通块，为了保持无序性，给每个连通块标号，设连通块数（点 \(i\) 度数）为 \(d\)。接下来分三种情况讨论。
-
\(u\)，\(v\) 处于 \(i\) 的两个不同连通块中（\(2 \le d\)）。此时贡献是 \(\sum_{x \le y \le d} sz_x \times sz_y \times (n - sz_x - sz_y)\)（\(x\)，\(y\) 代表连通块编号，\(sz\) 代表大小）。我们把式子拆开，不难发现分别维护 \(sz\) 和 \(sz ^ 2\) 的前缀和，扫一遍即可做到 \(\mathcal{O}(d)\) 计算。
-
\(u\)，\(v\) 中一个是 \(i\)，另一个位于一个连通块中。此时贡献是 \(\sum_{x \le d} sz_x \times (n - sz_x)\)。直接可以 \(\mathcal{O}(d)\) 扫一遍计算。
-
\(u\)，\(v\) 都重合，均在 \(i\) 上，贡献为 \(n\)。
计算一个点 \(i\) 的时间复杂度是 \(O(d_i)\)，那么计算全部的点的时间复杂度便是 \(O(\sum d)\)，然后考虑到一条边只会被计算两次，所以最终是 \(O(n)\) 的。
口胡的思路，一些细节可能会错，大体思路应该对完了。